Minimum Travel Time with One Stop

You are given N cities numbered from 1 to N and M bidirectional flights. Each flight connects two cities with a specified travel time. Your task is to determine the minimum possible travel time from city 1 to city N if you must choose exactly one flight to serve as a designated intermediate connection.

The journey is divided into three segments:

• A (possibly multi-hop) path from city 1 to some city a.
• A direct flight from city a to city b (this is the chosen intermediate flight).
• A (possibly multi-hop) path from city b to city N.

You are allowed to use the flights in either direction. The overall travel time is computed as:

$$\min_{(a,b,t) \in \text{flights}} \{ d(1,a) + t + d(b,N),\; d(1,b) + t + d(a,N) \} $$

where \(d(x,y)\) is the shortest travel time between cities \(x\) and \(y\) determined over the graph of flights. If no valid journey exists, output -1.

inputFormat

The first line contains two integers N and M which represent the number of cities and flights respectively. The following M lines each contain three integers u, v, and t, denoting that there is a flight between cities u and v with a travel time of t.

outputFormat

Output a single integer representing the minimum travel time from city 1 to city N making use of exactly one designated intermediate flight. If such a journey is not possible, output -1.

## sample

5 6
1 2 5
2 5 4
1 3 7
3 4 3
4 5 1
2 4 6

9