Minimizing Maximum Inconvenience in Yuland

Yuland is a small town consisting of \(n\) cities connected by \(m\) bidirectional roads. Each road has a positive length (which may differ from road to road), and there may be multiple roads connecting the same pair of cities. It is guaranteed that every city is reachable from any other city.

In each city, you may build either a rabbit shop or a duck shop (but not both). The residents of every city want to have access to both types of animals. For any city \(i\), define its inconvenience as \[ I(i)=\max\Big( d(i,\text{rabbit}),\; d(i,\text{duck}) \Big), \] where \(d(i,\text{rabbit})\) is the shortest distance from city \(i\) to any city with a rabbit shop and \(d(i,\text{duck})\) is defined similarly. Note that if a city builds a shop of a given type then the distance to that type is \(0\).

Your task is to help the mayor decide whether to build a rabbit shop or a duck shop in each city so as to minimize the maximum inconvenience over all cities. In other words, you should choose an assignment of shop types (rabbits or ducks) to each city so that if we define \[ M = \max_{1 \le i \le n} I(i), \] then \(M\) is minimized. It is not allowed to have all cities choose the same shop type.

inputFormat

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

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\), meaning that there is a bidirectional road between city \(u\) and city \(v\) with length \(w\) (\(1 \le u,v \le n\)).

outputFormat

Output a single integer: the minimized maximum inconvenience among all cities with an appropriate assignment of shop types. If no valid assignment exists, output an appropriate error (however, it is guaranteed that \(n\ge2\) so that a valid assignment exists).

sample

3 3
1 2 10
2 3 1
1 3 100

10