#P4289. PA2012 Tax

    ID: 3509 传统题 2000ms 128MiB 尝试: 2243 已通过: 390 难度: 7 上传者: 标签>CF2200提高+/省选-状态扩展图排序链优化建图超级源汇Dijkstra优化建图

PA2012 Tax

题目描述

给出一个 nn 个点 mm 条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点 11 到点 nn 的最小代价。起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权。保证存在从 11 到 nn 的路线。

输入格式

第一行两个数 n,mn,m,分别表示点数和边数。

接下来 mm 行,每行三个数 a,b,ca,b,c,表示 a,ba,b 之间存在一条长度为 cc 的边。

输出格式

一行一个数,表示答案。

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

提示

2≤n≤1052\leq n\leq 10^5,1≤m≤2×1051\leq m\leq 2\times 10^5,1≤c≤1061\leq c\leq 10^6。

题目来源