Minimum Magical Difficulty

You are given a directed graph with n stones (nodes) numbered from 1 to n and m pathways (edges). Each edge is defined by three integers u, v and w where there is a directed edge from stone u to stone v with magical difficulty w.

Your task is to determine the minimum magical difficulty required to complete the journey from stone 1 to stone n. You are allowed to choose exactly one pathway in which the cost is doubled (i.e. the magical difficulty along that edge is applied twice) if it helps to lower the total magical difficulty. Note that you may also choose to not double any edge.

Formally, let d(1, u) denote the minimum cost from stone 1 to stone u and d(v, n) denote the minimum cost from stone v to stone n in the original graph. The answer is the minimum among:

\(d(1, n)\)

and for each edge \((u, v, w)\):

\(d(1, u) + 2\times w + d(v, n)\)

If a path does not exist, you can assume that the magical difficulty is infinite and such route should not be considered.

inputFormat

The input is given via stdin and has the following format:

 n m
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm

Where n is the number of stones, m is the number of pathways, and each of the following m lines contains three integers representing an edge from stone u to stone v with magical difficulty w.

outputFormat

The output should be written to stdout which is a single integer representing the minimum magical difficulty required to complete the journey.

## sample

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

6