题目背景

弱化版的原题使用随机数据。考试中若遇到专门构造的图，SPFA 可能无法在时限内完成。标准版《单源最短路径》中的数据可用于比较。

题目描述

给出一张有向图以及一个出发点 $s$ ，求从 $s$ 到图中每个顶点的最短路径长度。

首行给出三个整数 $n,m,s$ ，依次为点数、有向边数和源点编号。

随后 $m$ 行各含三个整数 $u,v,w$ ，表示一条从 $u$ 指向 $v$ 、长度为 $w$ 的边。

输出一行 $n$ 个整数，依次表示 $s$ 到顶点 $1$ 至 $n$ 的最短距离。无法到达的顶点输出 $2^{31}-1$ ，即 2147483647。

0 2 4 3

原题的分档数据范围如下。

数据比例	条件
20%	$1\le n\le5,\ 1\le m\le15$
40%	$1\le n\le100,\ 1\le m\le10^4$
70%	$1\le n\le1000,\ 1\le m\le10^5$
100%	$1\le n\le10^4,\ 1\le m\le5\times10^5,\ 1\le u,v\le n,\ w\ge0,\ \sum w<2^{31}$

原题使用随机数据。2022 年 7 月 29 日的更新特别说明，同一对顶点之间可能有多条边。标准版《单源最短路径》的数据范围与本题略有不同。

样例说明

样例各条有向边的权值及最短路

图中每条有向边的标号表示其权值。源点为 $1$ ，到自身的距离为 $0$ 。到 $2$ 直接走权为 $2$ 的边。到 $3$ 经过 $2$ ，路程为 $2+2=4$ 。到 $4$ 也经过 $2$ ，路程为 $2+1=3$ 。