题目描述

给定一张无向图,求一条经过边数最少的从点1到点N的最短路。

对于30%:N <= 10

对于60%:N <= 1000

对于100%:N <= 50000, M <= 100000,0 <= 所有的边权 <= 10^9,保证存在从点1到点N的路径。可能有重边,自环。

时限:1s

内存限制:256MB

输入格式

第一行两个整数N,M,表示点数和边数。

接下来M行每行三个整数,表示一条无向边的两端和它的边权。保证点的编号在[1, n]内。

输出格式

一行两个整数,表示该最短路的长度,以及其经过的边数

如需输出64位整数,请使用cout或者printf("%I64d")。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论