P6822 [PA 2012 Finals] Tax

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.

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 one integer on a single line, representing the answer.

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