题目描述

给定一个包含 $n$ 个点和 $m$ 条边的有向图，其中可能存在重边和自环，所有边的权值均为正值。你需要计算从1号点到 $n$ 号点的最短路径长度。如果无法到达，则输出 -1。

输入格式

• 第一行包含两个整数 $n$ 和 $m$，分别表示图中的点数和边数。
• 接下来 $m$ 行，每行包含三个整数 $x, y, z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。

输出格式

• 输出一个整数，表示从1号点到 $n$ 号点的最短路径长度。
• 如果不存在路径，则输出 -1。

数据范围

• $1 \leq n \leq 500$
• $1 \leq m \leq 10^5$
• 图中边的长度不超过 $10^4$

输入示例

3 3
1 2 2
2 3 1
1 3 4

输出示例

3