PROGRAMMING:KK rumors
KK, a stockbroker, wants to spread a rumor among a group of people (the number of n people is 0 ~ n-1). The rumor is only passed through the people he knows. The time required to pass a message between two people he knows is different. In a group of people, KK wants to find out who is the starting point to pass the rumor. He can recognize that all people receive the message in the shortest time.
Please write a program to help KK solve this problem.
###Input format:
First, enter n m, where n is the number of people and M is the number of crowd relations that can deliver messages. Enter a b t in the following M lines respectively, which means that a can deliver messages to B, and the time consumed is t.
When you enter 0, it means the end of the input.
###Output format:
It takes the shortest time to transmit rumors from the first person. If there is no solution, output - 1.
###Input example:
Here is a set of inputs. For example:
```in
4 4
0 1 2
0 2 5
0 3 1
2 3 3
6 5
0 1 2
0 2 5
0 3 1
2 3 3
4 5 2
0
```
###Output example:
The corresponding output is given here. For example:
```out
three
-1
```
answer：If there is no answer, please comment
Please write a program to help KK solve this problem.
###Input format:
First, enter n m, where n is the number of people and M is the number of crowd relations that can deliver messages. Enter a b t in the following M lines respectively, which means that a can deliver messages to B, and the time consumed is t.
When you enter 0, it means the end of the input.
###Output format:
It takes the shortest time to transmit rumors from the first person. If there is no solution, output - 1.
###Input example:
Here is a set of inputs. For example:
```in
4 4
0 1 2
0 2 5
0 3 1
2 3 3
6 5
0 1 2
0 2 5
0 3 1
2 3 3
4 5 2
0
```
###Output example:
The corresponding output is given here. For example:
```out
three
-1
```
answer：If there is no answer, please comment