Travel Tax

The ruler of the kingdom of Byteotia, following a worldwide trend, has decided to tax everything that can be taxed. The most recently introduced levy is the so-called travel tax, which must be paid by everyone who moves around the country.

Every road in Byteotia has an assigned tax rate. When you pass through a city during a journey, you must pay a tax at that city's office equal to the maximum of the rate on the road by which you entered the city and the rate on the road by which you leave it. You also pay in the starting city and in the destination city of the journey; there, since only one road is used, the tax is computed from that single road alone.

Your friend Byteasar is setting out on a journey from city $1$ to city $n$. Help him plan a route so that he pays as little tax as possible.

The first line contains two integers $n$ and $m$ ($2 \le n \le 100\,000$, $1 \le m \le 200\,000$), the number of cities and the number of roads in Byteotia. Cities are numbered from $1$ to $n$.

Each of the next $m$ lines describes one road: the $i$-th such line contains three integers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 1\,000\,000$). They mean that cities $a_i$ and $b_i$ are connected by a two-way road whose tax rate is $c_i$ bytalers. There is at most one road between any pair of cities.

Print a single integer: the minimum cost of the journey (in bytalers) from city $1$ to city $n$. You may assume that a sequence of roads connecting these two cities always exists.

For example, suppose the roads are $\{1,2\}$ with rate $5$, $\{1,3\}$ with rate $2$, $\{2,3\}$ with rate $1$, $\{2,4\}$ with rate $4$, and $\{3,4\}$ with rate $8$. The optimal route runs through cities $1 \to 3 \to 2 \to 4$. The taxes paid at these cities are $2$, $\max(2, 1) = 2$, $\max(1, 4) = 4$, and $4$, which add up to $12$.