The ruler of the kingdom of Byteland, following a global trend, has decided to tax everything possible. The most recently introduced levy is the so-called travel tax, which must be paid by anyone traveling across the country.

Every road in Byteland is assigned a specific tax rate. When traveling through Byteland, every time we pass through a city, we must pay a tax at the local office, which is calculated as the maximum of the tax rate of the road we used to enter the city and the tax rate of the road we use to leave the city. Taxes are also paid in the starting and destination cities of the journey; in these cases, the tax is calculated by considering only the single road used to enter or leave that city.

Your friend Bytazar is planning a trip from Bytown to Bytawa. Help him plan his route so that he pays the lowest possible total tax.

Input

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

The next $m$ lines contain descriptions of the roads: the $i$-th line contains three integers $a_{i}$, $b_{i}$, and $c_{i}$ ($1 \le a_{i}, b_{i} \le n$, $a_{i} \ne b_{i}$, $1 \le c_{i} \le 1\,000\,000$). These indicate that cities $a_{i}$ and $b_{i}$ are connected by a bidirectional road with a tax rate of $c_{i}$ bajtalars. There is at most one road between any pair of cities.

Output

The first and only line of output should contain a single integer: the minimum cost of the journey (in bajtalars) from Bytown (city number 1) to Bytawa (city number $n$). You may assume that there is always a sequence of roads connecting these cities.

Examples

Input 1

4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8

Output 1

12

Note

In the example above, the optimal route passes through cities 1, 3, 2, and 4. We pay taxes in these cities of 2, max(2, 1) = 2, max(1, 4) = 4, and 4, respectively, which gives a total of 12 bajtalars.