You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

一天，YYZ 要坐飞机旅游全球去领略大千世界，她想从北京 fly 到 n 个城市，输入一 个世界地图，每个城市到城市有一个路程，由于 YYZ 只有留下的一点点财产，请帮帮他， 求出从我们的首都北京（源点）到所有城市的最短路径。

Input Format

第一行有两个整数 n 和 m。n 点表示顶点个数（顶点编号为 1~n）m 表示边的条数。接 下来 m 行，每行有 3 个数：x y z，表示顶点 x 到顶点 y 边的权值为 z(有向边)。 n、m<=10

Output Format

输出源点到所有顶点的最短路径

6 9 
1 2 1 
1 3 12 
2 3 9 
2 4 3 
3 5 5 
4 3 4 
4 5 13 
4 6 15 
5 6 4

0 1 8 4 13 17