1386: 【模板】单源最短路径

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

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

0 2 4 3

数据范围】
对于 $20\%$ 的数据：$1\le n\le 5$，$1\le m\le 15$；
对于 $40\%$ 的数据：$1\le n\le 100$，$1\le m\le 10^4$；
对于 $70\%$ 的数据：$1\le n\le 1000$，$1\le m\le 10^5$；
对于 $100\%$ 的数据：$1\le n\le 10^5$，$1\le m\le 5\times 10^5$，$1\le u,v\le n$，$w\ge 0$，$\sum w<2^31$，保证数据随机。

两个点之间可能有多条边，敬请注意。

$s=1$；

$1\le ui,vi\le n$；

$0\le wi\le 10^9$,

$0\le \sum wi\le 10^9$。