当前没有测试数据。

1.网络传输

题目描述

给定$n$个点$m$条边的带边权有向图，沿边方向传输信息的代价为该边的边权。特殊的是，同一个强连通分量内的点间传输代价为$0$。求点$1$到点$n$的最小传输代价。

输入格式

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

接下来$m$行，每行三个整数$u$，$v$，$w$；表示从点$u$到点$v$传输信息的代价为$w$。

输出格式

输出文件仅一行，为最短传输时间。

数据范围与提示

• 对于$40\%$的数据，$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}$。

样例

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

3