题目描述
给定一张无向图,求一条经过边数最少的从点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")。
样例输入
样例输出