题目背景

廉价航空的票价毫无规律：直飞有时贵得离谱，绕一次远路反而便宜。但旅客最在意的往往不是钱，而是少折腾。

题目描述

某国有 $n$ 座城市，编号 $1$ 到 $n$。城市之间有 $m$ 条单向航线，第 $i$ 条航线从城市 $u_i$ 飞往城市 $v_i$，票价为 $c_i$。

一条从城市 $1$ 到城市 $n$ 的行程由若干条航线首尾相接组成。行程的中转次数等于行程中包含的航线数减一（行程恰好只含一条航线时，中转次数为 $0$）。

旅客按如下次序挑选行程：

1. 先让中转次数尽可能少；
2. 再在所有中转次数最少的行程中，让总票价尽可能少。

请你输出最少的中转次数，以及在所有最少中转次数的行程中最小的总票价。如果城市 $1$ 无法到达城市 $n$，输出 -1。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,c_i$。

输出格式

一行两个整数：最少中转次数与对应的最小总票价；若无法到达则输出 -1。

输入输出样例 #1

输入 #1

4 5
1 2 100
1 3 1
3 4 1
2 4 1
4 3 1

输出 #1

1 2

说明

样例解释

从 $1$ 到 $4$ 至少要中转 $1$ 次。中转 $1$ 次的行程有 $1\to 2\to 4$ 与 $1\to 3\to 4$，票价分别为 $101$ 与 $2$，取较小者 $2$。

数据范围

• 对于 $100\%$ 的数据，$2\le n\le 2\times 10^5$，$1\le m\le 5\times 10^5$，$1\le c_i\le 10^9$。
• 同一条航线可能重复给出，也可能出现 $u_i=v_i$ 的航线。