Worst-Case Shortest Travel Time

Mike has discovered that his new girlfriend's enemy, Marika, is planning a long-distance trip to get revenge. They live in a country consisting of n cities connected by m bidirectional roads, where each road has an associated travel time (in minutes). There is at most one road between any two cities. Marika starts her journey from her city (city 1) to Mike's city (city n).

However, one of the roads is under repair and is jam‐ped, but Marika does not know which one. Regardless of which road is affected, it is guaranteed that there is always an alternative route from city 1 to city n that does not include the blocked road. Marika will only travel on roads that are not blocked and will always choose a route with the minimum total travel time.

Mike wants to know the worst-case scenario – that is, over all possible choices of one road being blocked, what is the maximum time Marika might require if she takes the shortest available path?

Formally, let \(G=(V,E)\) be the graph where each edge \(e\in E\) has a travel time \(w_e\). For every edge \(e\), define \(d_e\) as the shortest distance from city 1 to city n in the graph \(G\setminus\{e\}\). You need to compute \(\max_{e \in E} d_e\). Note that all formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains two integers n and m, representing the number of cities and roads respectively.

The following m lines each contain three integers u v w, indicating that there is a bidirectional road between city u and city v with travel time w (in minutes).

It is guaranteed that for any road \(e\) (i.e. for every edge), the graph \(G\setminus\{e\}\) has a path from city 1 (Marika's city) to city n (Mike's city).

outputFormat

Output a single integer, the maximum among the shortest travel times from city 1 to city n when each road is blocked one at a time.

sample

4 5
1 2 5
2 3 10
3 4 5
1 3 15
2 4 20

25