Problem I: 出行方案

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $16$ 正确数量 $4$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论
安科的夏天真是不一般的热,避免炎热,伍学长因此想为自己规划一个校园出行方案,使得从宿舍出发到校园的各个地方距离花费时间最短。我们已知校园一共有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个路口的最小花费时间及步行方案


输入包括多组数据。每组数据第一行是两个整数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分钟的时间走过这条路。

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

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