题目描述
给定 $n$ 个点 $m$ 条边的带边权有向图，沿边方向传输信息的代价为该边的边权，特殊的，同一个强联通分量内的点间传输代价为 $0$，求点 $1$ 到点 $n$ 的最小传输代价
输入
第一行两个整数 $n,m$，表示有 $n$ 个点，$m$ 条边。
接下来 $m$ 行，每行三个整数 $u,v,w$；表示从点 $u$ 到点 $v$ 传输信息的代价为 $w$。
输出
输出文件仅一行，为最短传输时间。
样例输入输出
输入#1
复制
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2
提示
对于 $30\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq m \leq 10^4$。
对于 $70\%$ 的数据，$1 \leq n \leq 5 \times 10^3$，$1 \leq m \leq 10^5$。
对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^6$。