#P6822. [PA2012] Tax
[PA2012] Tax
题目描述
给出一个 个点 条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点 到点 的最小代价。起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权。
输入格式
第一行两个数 ,分别表示点数和边数。
接下来 行,每行三个数 ,表示 之间存在一条长度为 的边。
输出格式
一行一个数,表示答案。
4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8
12
提示
,,。