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

输入描述:

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

输出描述:

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