F-坐火车_2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛)

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$G$ 国有 $n$ 个城市，城市之间由 $m$ 条双向直达铁路连接，一条铁路连接了两个不同的城市，并且乘坐第 $i$ 条铁路需要 $w_i$ 个单位时间。如果两个城市之间没有直达的铁路，那么则必须要通过其他城市换乘才能相互可达。换乘不需要花费时间，但是 lbromine 非常不喜欢换乘。现在 lbromine 想要从 $1$ 号城市到达 $n$ 号城市，他想知道他最少需要经过多少个城市(包括城市 $1$ 和城市 $n$ )，以及在保证经过城市最少的情况下需要花费的最少时间。

输入描述:

第一行两个正整数  表示 国有  个城市和  条铁路。

接下来  行，每行三个整数  表示 lbromine 可以花费  的时间在  和  之间旅行。

数据保证  号城市和  号城市联通。

输出描述:

输出一行两个整数，第一个整数表示lbromine最少需要经过多少个城市，第二个整数表示保证经过城市最少的情况下需要花费的最少时间，两个整数之间用空格隔开。

示例1

输入

复制

输出

复制

2 5

备注:

对于  的数据，

对于  的数据，

对于  的数据，