题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

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

```output1 1

0 2 1

## 样例 #2
```input1 2

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

```output1 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$
- 图中允许存在重边、自环