题目描述

给定一个包含 $n$ 个节点、$m$ 条边的有向带权图，边权可以为正数、负数或0，题目保证图中不存在负权环。

请你求出从源点 $s$ 出发，到图中每个节点的最短路径长度。若节点无法从源点 $s$ 到达，请输出 inf。

输入格式

第一行三个整数 $n, m, s$，分别表示图的节点数、边数、源点编号。节点编号从 $1$ 到 $n$。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示一条从节点 $u$ 指向节点 $v$、权值为 $w$ 的有向边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数对应源点 $s$ 到节点 $i$ 的最短路径长度，无法到达则输出 inf。

样例 #1

样例输入 1

3 3 1
1 2 2
2 3 -1
1 3 5

样例输出 1

0 2 1

样例 #2

样例输入 2

4 3 1
1 2 5
1 3 -2
3 4 3

样例输出 2

0 5 -2 1

数据范围

• $1 \le n \le 1000$
• $1 \le m \le 5000$
• $1 \le s \le n$
• $-10^5 \le w \le 10^5$
• 图中允许存在重边、自环