Description

Given an undirected graph with $n$ vertices and $m$ edges, the cost of passing through a vertex is the larger of the weights of the two edges used to enter and leave this vertex. Find the minimum total cost from the start vertex $1$ to vertex $n$. The cost at the start vertex is the weight of the edge leaving the start vertex, and the cost at the end vertex is the weight of the edge entering the end vertex.

Input Format

The first line contains two integers $n,m$, representing the number of vertices and the number of edges.

The next $m$ lines each contain three integers $a,b,c$, meaning there is an edge of length $c$ between $a$ and $b$.

Output Format

Output one integer on a single line, representing the answer.

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

12

Hint

Constraints: $1\leq n\leq 10^5$，$1\leq m\leq 2\times 10^5$，$1\leq c\leq 10^6$。

Translated by ChatGPT 5