TORONTO KIDS COMPUTER CLUB | Aurora Saturday 14:30 Python Practice 22.04.09.
20538

# Aurora Saturday 14:30 Python Practice 22.04.09.

## 14 Apr Aurora Saturday 14:30 Python Practice 22.04.09.

Question:
The clothing factory made very nice t-shirts. But it’s very tired for the staff to get hundreds of pieces of clothing shipped to the store! So they want to find the shortest route to the store from the clothing factory, you can help them?

Input Format
There are multiple test cases. Each case starts with a line contains two integers N, M (N <= 100 , M <= 10000), N represents the number of intersections in the city, the factory is located at intersection number 1, the store is located at the intersection number N, M indicates a couple of route choices in the city. N = M = 0 indicates the end of input.

In next M rows, each row contains three integers A, B, C (1 < = A, B <= N, 1 <= C <= 1000), indicates there is a route between the intersection A and the intersection B, and it takes C minutes to travel from A to B.
There is at least one route from the factory to the store.

Output Format
For each test case, print the minimum minutes needed from factory to the store.

`SAMPLE INPUT2 11 2 33 31 2 52 3 53 1 20 0Sample Output32`