给定一张 $n$ 个点 $m$ 条边的带权有向图，权值可能为负，求起点 $s$ 到所有点的最短路。

输入格式

第一行三个由空格隔开的整数 $ n $、$ m $、$ s $。

之后的 $ m $ 行，每行三个正整数 $ s_i $、$ t_i $、$w_i$ ($1 \le s_i, t_i \le n$, $-10^9 \leq w_i \leq 10 ^ 9$) ，表示一条从 $ s_i $ 到 $ t_i $ 长度为 $ w_i $ 的有向边。图中可能存在重边或自环。

输出格式

输出一行，包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$。其中 $d_i$ 表示从 $s$ 到 $i$ 的最短路长度。如果不存在对应的道路，输出 N/A。如果对应的最短路为负无穷，输出 -inf

样例数据

样例 1 输入

4 5 1
1 2 1000
2 3 10000
3 1 1
3 4 100000
3 4 1000000

样例 1 输出

0 1000 11000 111000

样例 2 输入

4 4 2
1 2 1
2 3 1000000000
3 4 -1
4 3 -1

样例 2 输出

N/A 0 -inf -inf

子任务

对于所有数据，$1 \le n \le 5\,000$，$0 \le m \le 3 \cdot 10^5$。