题目描述

长江游艇俱乐部生意火爆，为了满足不同游客的需求，俱乐部推出了“超级会员”服务。普通游客只能顺流而下，但超级会员可以使用俱乐部特配的强力摩托艇，不仅可以顺流而下，还可以在特定的航道上逆流而上或者进行跳跃式航行。

长江上设置了 $n$ 个游艇出租站，编号为 $1, 2, \dots, n$。

俱乐部在这些站点之间开通了 $m$ 条单向航线。第 $i$ 条航线从站点 $u_i$ 出发到达站点 $v_i$，费用为 $w_i$。

请注意：

航线不局限于从小编号到大编号，可能存在从大编号到小编号的航线（即逆流航线）。

两个站点之间可能存在多条费用不同的航线。 整个航线网络中可能包含环。

现在的目标依然是从站点 $1$ 出发，到达站点 $n$。作为一个精打细算的超级会员，请你计算出最少需要花费多少租金。

输入格式

第一行包含两个正整数 $n$ 和 $m$，分别表示游艇出租站的数量和航线的数量。

接下来 $m$ 行，每行包含三个正整数 $u, v, w$，表示存在一条从站点 $u$ 到站点 $v$ 的单向航线，租金为 $w$。

输出格式

输出一个整数，表示从站点 $1$ 到站点 $n$ 的最小租金。如果无法到达站点 $n$，则输出 -1。

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 100$，$1 \le m \le 500$。

• 对于 $100\%$ 的数据，$1 \le n \le 100,000$，$1 \le m \le 200,000$，$1 \le w \le 10^4$。

• 保证起点 $1$ 至少连通一条边。

输入样例:

3 3
1 2 5
2 3 5
3 1 1

输出样例：

10