在世界的另一端，有一个美丽富饶的精灵大陆，那里存在着六个城市，城市中生存着许多小精灵。一开始，这个大陆和平安详，没有纷争，但是有一天，邪恶黑暗势力忽然侵袭统治了这片大陆，并把大陆中的六个城市用黑暗力量染成了黑色，精灵们感到十分恐惧。这时,光明之神派遣一只被称为“番长狮子"（名字叫“亚历山大”）的英雄带领军队前往解救（“番长”是精灵大陆中一个很厉害的称号，只有实力非常强大的生灵才能拥有）。由于黑暗力量的影响，城市与城市之间只能通过某种特殊通道单向到达（即有向边），并且一些城市之间无法直接到达（即只能通过其他城市间接到达）。下图给出了六个城市（编号为从V0至V5）和它们之间存在的有向边（边上的数字表示距离），且每个城市都被污染成了黑色（表示该城市暂时没有被解救）。亚历山大在研究地图后决定从V0开始对六个城市的敌人发起进攻，且每成功攻下一个城市，就用光明之力让城市中的黑暗消散，并把带来的部队驻扎在城市中，以防黑暗势力攻回，自己则通过魔法重新回到V0，带领新的部队攻打下一个城市。为了减少消耗，亚历山大希望每次从起点V0到达需要攻占的城市之间的路程尽可能短，即从起点到达其他所有顶点都必须是最短距离。

第一行，三个数据分别表示顶点个数、边数、起点编号。
接下来m行，分别表示一条边的点u与点v的标号，以及边权。

一行，表示起点到每个点的最短路径。