No testdata at current.

题目描述

外星人又双叒叕攻打土拨鼠星球了,土拨鼠们为了防御建立了n个根据地,由m条地道相连,$w{\tiny i}$表示每个战士经过第i条边所消耗的士气值,现在指挥部想向每个根据地分别派发一名士兵,请求出这个士兵到达根据地后消耗的最少士气值.

也就是给出一个n个点,m个有向边,求从s点出发,到达每个点的最短路.题目保证不会出现负环和自己指向自己的边,但会有边权为负的边,但不保证所有点都能到达!

Format

Input

第一行输入两个数 n,m,s 接下来m行每行输入3个数,分别是这条边的起点终点和消耗的士气.

Output

输出n行每行一个数,第i行表示从s到i所消耗的最少士气值,如果不能到达则输出NO

Samples

5 6 1
2 1 31
3 2 52
3 4 11
4 5 14
1 5 -81
1 3 -10

0
42
-10
1
-81

Limitation

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$