题目描述

给定一张 有向带权图，点编号为 $1\sim n$。

你需要从点 $1$ 走到点 $n$。在整条路径上，你 必须且只能 选择 一条边 使其费用变为 $0$，其余边仍按原费用计算。

请你求出最小总花费。

如果无法从 $1$ 到达 $n$，输出 -1。

输入格式

第一行两个整数 $n,m$，表示点数和边数。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条从 $u$ 指向 $v$ 的有向边，边权为 $w$。

• $2 \le n \le 2\times 10^5$
• $1 \le m \le 4\times 10^5$
• $1 \le u,v \le n$
• $1 \le w \le 10^9$
• 图中 可能存在重边和自环。
• 边权均为正整数。

输出格式

输出一个整数，表示最小总花费；若不存在从 $1$ 到 $n$ 的路径，输出 -1。

4 4
1 2 100
2 4 1
1 3 60
3 4 60

1

3 1
1 2 5

-1

5 7
1 2 8
2 5 8
1 3 3
3 4 100
4 5 3
2 3 1
1 5 50

0