Description

A tomb raider sneaks into a pyramid to steal treasure. When she (could it be Lara Croft?) opens a treasure chest, a sudden puff of smoke appears (Pandora's box?). She quickly realizes the danger and decides to flee. Since she has the pyramid’s map, she hopes to find the best escape route. The map shows $N$ rooms. She is currently in room $1$, and the exit is in room $N$. She knows a secret: the smoke will halve her running speed in the corridor that directly connects some pair of rooms. She wants to find an escape route that minimizes the time used in the worst case.

Input Format

The first line contains two positive integers $N$ ($3 \le N \le 100$) and $M$ ($3 \le M \le 2000$).
Each of the following $M$ lines contains three positive integers $U$, $V$, and $W$, indicating that running directly between room $U$ and room $V$ takes $W$ seconds ($3 \le W \le 255$).

Output Format

Output the minimal possible time, in seconds.

7 8
1 2 10
2 3 12
3 4 20
4 7 8
1 7 34
2 5 10
5 6 12
6 4 13

66

Hint

Sample Explanation:

There are essentially three routes:

(1) $1 \to 2 \to 3 \to 4 \to 7$.
Total time: $10 + 12 + 20 + 8 = 50$. In the worst case, the segment $3 \to 4$ takes twice as long, costing an extra $20$ seconds, so this route takes $70$ seconds in the worst case.

(2) $1 \to 2 \to 5 \to 6 \to 4 \to 7$.
Total time: $10 + 10 + 12 + 13 + 8 = 53$. In the worst case, the segment $6 \to 4$ takes twice as long, costing an extra $13$ seconds, so this route takes $66$ seconds in the worst case.

(3) $1 \to 7$.
Total time: $34 = 34$. In the worst case, the segment $1 \to 7$ takes twice as long, costing an extra $34$ seconds, so this route takes $68$ seconds in the worst case.

Translated by ChatGPT 5