题目背景

2018 年 7 月 19 日的 NOI 第一天，第一题是《归程》。有位选手熟练地用一种大家熟悉的最短路算法解了这道题。

这道题的成绩从 $100$ 分变成了 $60$ 分，原先有望拿到的银牌也变成了铜牌。他最终没能和自己心仪的大学签约。小 F 希望后来的选手能从这段经历中吸取教训。

题目描述

给定一张包含 $n$ 个顶点、$m$ 条有向边的图，每条边的权值都非负。求源点 $s$ 到各顶点的最短距离。

保证从 $s$ 出发可以到达图中的每一个顶点。

输入格式

首行是三个正整数 $n,m,s$，分别表示点数、有向边数与源点编号。

接下来的 $m$ 行各给出三个非负整数 $u_i,v_i,w_i$。这条有向边由 $u_i$ 指向 $v_i$，权值为 $w_i$。

输出格式

输出一行 $n$ 个非负整数，依次为 $s$ 到顶点 $1$ 至 $n$ 的最短距离。

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

说明/提示

样例说明

本题与弱化版使用相同的样例。

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

数据范围

• $1\le n\le10^5$，$1\le m\le2\times10^5$，$s=1$。
• $1\le u_i,v_i\le n$，$0\le w_i\le10^9$。
• 所有边的权值之和满足 $0\le\sum w_i\le10^9$。

原题的数据可能继续更新，更新后不重测此前提交的程序。原题曾于 2018 年 9 月 4 日更新数据。