对于给定的由 个顶点、 条边构成的有向赋权图（不一定连通），权值仅为非负整数。依次输出以顶点 为起点、到全部顶点的最短路径长度。 提示 本题为 模板题，您应当需要使用其堆优化的版本，预期实现时间复杂度为 。 特殊测试点信息： 测试点 稀疏图； 测试点 菊花图； 测试点 稠密图； 测试点 边权仅为 ； 测试点 链； 测试点 网格图； 测试点 劣化 的复杂度。

输入描述:

第一行输入三个整数 代表顶点数量、边数量、起点编号。此后 行，第 行输入三个整数 和 表示图上第 条边单向连接顶点 和 、边权为 。图可能不连通、可能存在重边。不存在自环。

输出描述:

在一行上输出 个整数，依次代表到各个顶点的最短路径。特别的，若终点为自己，输出 ，若不存在路径，则输出 。