题目描述

给定一个 $n$ 个点 $m$ 条边的有向图，$1$ 号点为起点，$n$ 号点为终点，请找出两条从起点到终点不重复的路径，且这两条路径的长度之和达到最小。

所谓路径不重复，是指两条路径中没有重复的边，注意，不重复路径也可以经过同一个点。

输入数据保证起点到终点至少有两条不重复的路径。

输入格式

第一行：两个整数 $n$ 与 $m$； 第二行到第 $m+1$ 行 ：在第 $i+1$ 行有三个整数 $u_i$，$v_i$ 与 $w_i$，表示图上有一条从 $u_i$ 到 $v_i$ 的边长度为 $w_i$，数据保证 $u_i\neq v_i$。

输出格式

单个整数：表示两条从起点到终点不重复的路径的长度之和的最小值。

3 3
1 2 10
2 3 1
1 3 2

13

数据范围

• 对于 $30\%$ 的数据，$n\leq 500$，$m\leq 5000$；
• 对于 $60\%$ 的数据，$n\leq 5000$，$m\leq 200,000$；
• 对于 $100\%$ 的数据，$2\leq n\leq 200,000$，$m\leq 500,000$；
• $1\leq w_i\leq 100,000$。