Medicine Delivery

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fastest route from one settlement to the other along roads, pausing 5 minutes at equipment stations to wash whenever 100 minutes of driving would otherwise be exceeded.

Level: Medium6 of 10
Topics: Shortest path, Graph, Heap, Dynamic programming
Solved: No attempts yet

Problem

Two survey teams were sent to an uncharted planet whose surface is mostly desert, and they set up settlements. The desert is so barren and the sandstorms so fierce that a survey vehicle can only travel on paved roads, and it must wash off the sand with special equipment every so often. Otherwise the vehicle picks up too much sand and cannot move. Washing off the sand takes 5 minutes, and after washing, the vehicle can drive for up to 100 minutes without washing again. Special equipment is placed throughout the desert; there are N units in total, numbered 1 through N for management. Paved roads connect the settlements and the locations of the special equipment. No two paved roads meet anywhere except at their endpoints.

During the survey, a patient appears in one settlement, and it must receive medicine delivered from the other settlement. Find the minimum time for a survey vehicle to deliver the medicine.

Input

The first line gives the number of special equipment units N and the number of paved roads K, separated by a space. (0 ≤ N ≤ 1000; 1 ≤ K ≤ 3000)

Each of the next K lines gives integers u, v, t separated by spaces. (0 ≤ u, v ≤ N+1; 1 ≤ t ≤ 1000)

u and v are the endpoints of a road and denote management numbers of special equipment. If the number is 0, it is the settlement sending the medicine, and if it is N+1, it is the settlement receiving it. t is the time in minutes to travel from u to v (or from v to u).

It is always given that a vehicle can travel between the two settlements. Just before departure, all sand on the vehicle has been washed off.

Output

Output the minimum time in minutes for the survey vehicle to deliver the medicine.

Examples3

Example 1
Input
```
1 3
0 1 40
1 2 80
0 2 110
```
Expected output
```
125
```
Example 2
Input
```
0 1
0 1 100
```
Expected output
```
100
```

Example 3

Input

Expected output