#Pscc15. 1.网络传输

    ID: 601 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>强连通分量赛制:OI来源:wyfoj http://127.0.0.1

1.网络传输

1.网络传输

题目描述

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

输入格式

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

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

输出格式

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

数据范围

(原站未提供,导入后需人工补齐)

样例

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

提示

对于40%的数据,1<=n<=103,1<=m<=1041<=n<=10^3,1<=m<=10^4。

对于70%的数据,1<=n<=5∗103,1<=m<=1051<=n<=5*10^3,1<=m<=10^5。

对于100%的数据,1<=n<=2∗105,1<=m<=1061<=n<=2*10^5,1<=m<=10^6。