对于给定的由 个顶点、 条边构成的有向赋权图（不一定连通），权值仅为非负整数。依次输出以顶点 为起点、到全部顶点的最短路径长度。

输入描述:

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

输出描述:

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

备注:

本题已于下方时间节点更新，请注意题解时效性：1. 2025-12-01 优化题面文本与格式；缩小 的范围（从 缩小到 ）。模板题为便于测试，将时间限制扩充至 5s，空间限制扩充至 1024MB。