求最短路

题目描述:

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

输入格式:

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

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

输出格式:

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

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

样例输入:

3 3
1 2 1
2 3 1
1 3 2

样例输出:

2 1

提示:

//虽然1->2->3也是最短路，但是其经过的边数不是最少的。

 

对于30%：N <= 10

对于60%：N <= 1000

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

时间限制: 1000ms
空间限制: 256MB

---