题目内容

多多在一家电商平台做物流调度。平台在 $N$ 个城市之间建立了 $M$ 条有向运输线路，每条线路从城市 $u$ 到城市 $v$，需要支付邮费 $w$ 元。

一位顾客在城市 $1$ 下单，商品需要从城市 $1$ 运送到城市 $N$。多多手里恰好有一张免邮券，可以免除任意一条两个城市间有向运输线路的邮费（将该条线路的邮费变为 $0$）。

请帮助多多计算从城市 $1$ 到城市 $N$ 的最小总邮费。如果即使使用免邮券也无法到达城市 $N$，输出 $-1$。

输入描述

第一行两个整数 $N, M$，分别表示城市数量和运输线路数量。

其中 $N$ 表示共有 $N$ 个城市，$M$ 表示共有 $M$ 条有向运输线路。 $(2 \le N \le 100000,\ 0 \le M \le 200000)$

接下来 $M$ 行，每行三个整数 $u, v, w$，表示一条从城市 $u$ 到城市 $v$ 的有向运输线路，其中 $w$ 表示通过该线路需要支付的邮费。 $(1 \le u, v \le N,\ 1 \le w \le 10000)$

输出描述

输出一个整数，表示从城市 $1$ 到城市 $N$ 的最小总邮费。如果无法到达，输出 $-1$。

样例1

输入

4 4
1 2 2
1 3 5
2 4 3
3 4 1

输出

1

说明

• 不使用免邮券：最短路径 $1 \to 2 \to 4 = 2+3=5$，或 $1 \to 3 \to 4 = 5+1=6$，最小为 $5$
• 免邮 $1 \to 3$（邮费 $5 \to 0$）：走 $1 \to 3 \to 4 = 0+1=1$
• 免邮 $1 \to 2$（邮费 $2 \to 0$）：走 $1 \to 2 \to 4 = 0+3=3$
• 免邮 $2 \to 4$（邮费 $3 \to 0$）：走 $1 \to 2 \to 4 = 2+0=2$
• 免邮 $3 \to 4$（邮费 $1 \to 0$）：走 $1 \to 3 \to 4 = 5+0=5$

最优方案：免邮 $1 \to 3$，总邮费 $1$。