Optimal Escape Route in the Pyramid

A daring tomb raider has infiltrated an ancient pyramid. After opening a treasure chest, a mysterious cloud of smoke suddenly erupts. The raider quickly realizes danger – as the smoke slows her down in one of the corridors. Fortunately, she has managed to steal a map of the pyramid.

The pyramid consists of \(N\) chambers (numbered from 1 to \(N\)). The raider starts in chamber 1 and the exit is in chamber \(N\). The corridors connect some pairs of chambers and each corridor \(e\) has a travel time of \(t_e\) when there is no smoke. However, due to the smoke the walking speed on exactly one corridor in her chosen route is halved, effectively doubling the time on that corridor. In other words, if her route consists of corridors with weights \(t_1, t_2, \dots, t_k\) then in the worst case (when the corridor with the largest \(t_e\) gets affected by the smoke), her total time is \[ T = \left(\sum_{i=1}^{k} t_i\right) + \max_{1 \le i \le k} t_i. \]

The task is to choose a path from chamber 1 to chamber \(N\) that minimizes this worst-case total time.

Note: The corridors are bidirectional.

inputFormat

The input begins with a line containing two integers \(N\) and \(M\) where \(N\) is the number of chambers and \(M\) is the number of corridors.

Each of the next \(M\) lines contains three integers \(u\), \(v\) and \(t\) representing a corridor between chambers \(u\) and \(v\) with normal travel time \(t\) (without smoke).

outputFormat

Output a single integer: the minimum worst-case total time required to reach chamber \(N\) from chamber 1, where the worst-case time of a route is defined as \[ \left(\sum_{e \in path} t_e\right) + \max_{e \in path} t_e. \]

sample

3 3
1 2 3
2 3 5
1 3 10

13