PROGRAMMING:The shortest path problem
Given the traffic graph between N villages, if there is a road between villages I and j, the vertices I and j are connected by edges. Wij on the edge represents the length of the road. Now we need to select a village from n villages to build a hospital. Which village should the hospital be built in to make the shortest distance from the village farthest from the hospital to the hospital? Try to design an algorithm to solve the above problem, and apply the algorithm to solve the example as shown in the figure [test case: Fan Yiming, IOT engineering level 16]
###Input format:
There are several groups of input, the first line in each group has two numbers n (1 < = n < = 500), m; Where n is the number of teams and M is the input data of M lines. In the next M rows, each row also has three integers P1, P2, and W. It means that there is a path between P1 and P2, the length of which is w;
###Output format:
For each group of output, the output is suitable for the construction of the village hospital
###Input example:
Here is a set of inputs. For example:
```in
4 6
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
answer：If there is no answer, please comment
###Input format:
There are several groups of input, the first line in each group has two numbers n (1 < = n < = 500), m; Where n is the number of teams and M is the input data of M lines. In the next M rows, each row also has three integers P1, P2, and W. It means that there is a path between P1 and P2, the length of which is w;
###Output format:
For each group of output, the output is suitable for the construction of the village hospital
###Input example:
Here is a set of inputs. For example:
```in
4 6
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
answer：If there is no answer, please comment