题目背景

终于放寒假了，小许同学打算用存压岁钱的银行卡在网上买一些年货。谁能想到却连续三次输错了支付密码，导致银行卡都被冻结了。没办法，他只能在地图上看看附近哪里有银行营业厅，好去将银行卡解封。可是，在这座拥挤的城市里，所有的道路都是单行线，这让小许脑子里一团乱麻。现在，他想请你帮他查查，到每个营业厅的最短距离到底是多少呢？

题目描述

有一张n个顶点（标号为1~n），m条边的带权有向图，给定小许家的地点是x，其他顶点都是银行营业厅。请问他到各个银行的最短距离？

输入格式

第一行为三个正整数：n m x，接下来m行每行为三个非负整数 a b w，分别表示从a点指向b点有一条单向路径，长度为w

输出格式

输出一行 n 个空格分隔的整数，表示小许家x到每个地点的距离。

输入#1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出#1

0 2 4 3

数据范围：

1 \(\leq\) \(n\) \(\leq\) \(10^5\)
1 \(\leq\) \(m\) \(\leq\) \(2*10^5\)
\(x = 1\)
1 \(\leq\) \(a,b\) \(\leq\) n
1 \(\leq\) \(w_i\) \(\leq\) \(10^9\)