2014
02-10

# Distance

A city contains a number of streets connecting several junctions. All the streets are straight line segments connecting two junctions. The walking distance between two points (each either a junction or some intermediate point of a street) in the city is the shortest path from the first point to the second. You are allowed to walk only along the streets. Streets never intersect outside the junctions. Now, your goal is to find the maximal walking distance among any two points in the city.

The input file contains several test cases. Each test case begins with two integers n and m ( 1<=n<=50, 0<=m<=n*(n-1)/2 ), which are the number of junctions and the number of streets. The following m lines each contain 3 integers Xi, Yi and Si ( 0<=Xi,Yi<n, 0<Si<=1000) indicating there is a street connecting junction Xi to Yi and the length is Si.

The input file contains several test cases. Each test case begins with two integers n and m ( 1<=n<=50, 0<=m<=n*(n-1)/2 ), which are the number of junctions and the number of streets. The following m lines each contain 3 integers Xi, Yi and Si ( 0<=Xi,Yi<n, 0<Si<=1000) indicating there is a street connecting junction Xi to Yi and the length is Si.

1 0
2 0
2 1
1 0 100
4 3
0 1 1
0 2 2
0 3 3
4 4
0 1 2
1 2 3
2 3 4
3 0 8

0.0
-1
100.0
5.0
8.5

1. = =还有提一点 在命相上来说 手掌很红的人 血气旺盛脾气暴躁 容易得高血压 掌纹杂乱的人 说明心思细密 内心比较复杂 一般单纯脾气好的人 掌纹很少很少 颜色也是健康的嫩粉色的。嗯 所以交朋友 可以先从手相上看，掌纹多乱 特别红的人 慎重交往，很可能