随机数据下的最短路问题 ### 题目描述 给定 $N$ 个点和 $M$ 条单向道路，每条道路都连接着两个点，每个点都有自己编号，分别为 $1\sim N$ 。 问你从 $S$ 点出发，到达每个点的最短路径为多少。 ### 输入描述 输入第一行包含三个正整数 $N,M,S$。 第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\rightarrow v$ 之间存在一条距离为 $w$ 的路。 $1\leq N \leq 5\times10^3$，$1 \leq M \leq 5\times 10^4$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 9$。 本题数据随机生成。 ### 输出描述 输出仅一行，共 $N$ 个数，分别表示从编号 $S$ 到编号为 $1\sim N$ 点的最短距离，两两之间用空格隔开。（如果无法到达则输出 $-1$） ### 输入输出样例 #### 示例 1 >输入 ```txt 3 3 1 1 2 1 1 3 5 2 3 2 ``` >输出 ```txt 0 1 3 ```