Problem I: 出行方案

上一题 正确率: $25.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $16$ 正确数量 $4$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论

Description

安科的夏天真是不一般的热，避免炎热，伍学长因此想为自己规划一个校园出行方案，使得从宿舍出发到校园的各个地方距离花费时间最短。我们已知校园一共有N个路口，标号为1的路口是宿舍所在地，2..N这N-1这几个标号分别是学校的N-1个地方，

M则表示安科共有M条路，N=M=0表示输入结束，接下来M行，每行有3个整数A,B,C（1<=A,B<=N,1<=C<=1000），表示在路口A与B之间有一条路，伍学长从A走到B花费时间C，伍学长来回用时相等,他现在想知道他分别到这N-1个路口的最小花费时间及步行方案


Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示安科有几个路口，标号为1的路口是伍学长的宿舍所在地，N表示安科共有N个路口（包含宿舍），M则表示在安科有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，伍学长需要C分钟的时间走过这条路。

输入保证从宿舍到任何路口都有边

Output

对于每组输入，共有N-1行，第i行表示从宿舍到i个（i=2,...,N）路口的花费和路径，到第k（k>=2）个路口，路径格式为costK p1->p2->..->pk(costk表示到k最小花费的时间)

Sample Input复制

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output复制

3 1->2
5 1->2
2 1->3