### 问题描述 $G$ 国有 $n$ 个城市，城市之间由 $m$ 条双向直达铁路连接，一条铁路连接了两个不同的城市，并且乘坐第 $i$ 条铁路需要 $w_i$ 个单位时间。如果两个城市之间没有直达的铁路，那么则必须要通过其他城市换乘才能相互可达。换乘不需要花费时间，但是 lbromine 非常不喜欢换乘。现在 lbromine 想要从 $1$ 号城市到达 $n$ 号城市，他想知道他最少需要经过多少个城市**(包括城市 $1$ 和城市 $n$ )**，以及在保证经过城市最少的情况下需要花费的最少时间。 ### 输入格式 输入第 $1$ 行包含两个正整数 $n，m$ ，表示 $G$ 国有 $n$ 个城市和 $m$ 条铁路。 第 $2\sim m+1$ 行每行包含三个整数 $u_i,v_i,w_i$，表示 lbromine 可以花费 $w_i$ 的时间在 $u_i$ 和 $v_i$ 之间旅行。 **数据保证 $1$ 号城市和 $n$ 号城市联通。** ### 输出格式 输出一行，这一行包含两个整数，第一个整数表示 lbromine 最少需要经过多少个城市，第二个整数表示保证经过城市最少的情况下需要花费的最少时间，两个整数之间用空格隔开。 ### 样例输入 ``` 4 4 1 2 1 2 3 1 3 4 1 1 4 5 ``` ### 样例输出 ``` 2 5 ``` ### **说明/提示** 对于 $30\%$ 的数据，$1\leq n\leq 10\ ,\ n-1\leq m\leq 20$； 对于 $60\%$ 的数据，$1\leq n\leq 10^3\ ,\ n-1\leq m\leq 2\times 10^4$； 对于所有评测数据，$1\leq n\leq 10^5\ ,\ n-1\leq m\leq 2\times 10^5$。