問題文

ある日、shojin 王国に体重 $10^{10^9}[kg]$ のちょっぴりおでぶなおばけさんが引っ越してきました。

shojin 王国は $n$ 個の都市からなっており、都市には順番に都市 $1$ 、都市 $2$ 、 $\dots$ 、都市 $n$ と名前がついています。$m$ 本の道が都市同士を繋いであり、同様に道 $1$ 、道 $2$ 、 $\dots$ 、道 $m$ と名前がついています。 $i(1 \le i \le m)$ 番目の道は都市 $s_i$ と都市 $t_i(s_i \neq t_i)$ をつないでおり、双方向に通行可能です。すべての $1 \le a, b \le n$ について、いくつかの道を使い都市 $a$ から都市 $b$ にたどり着けることが保証されます。 また、$i$ 番目の道は $d_i[kg]$ までしか耐えられません。

おばけさんは最初都市 $1$ にいて、いくつかの道を通って都市 $n$ に行きたいです。

しかし、おばけさんの体重を $w[kg]$ としたとき、$w > d_i$ を満たす $i$ について、道 $i$ は崩壊の危険性があるため使えません。

ダイエットが上手ではないおばけさんのために、都市 $1$ から都市 $n$ に到達可能な体重 $w$ の 最大値 及び、$w$ が最大値の時都市 $1$ から都市 $n$ に到達するために通る必要のある道の数の 最小値 を求めてください。

制約

入力

$n\ m$
$s_1\ t_1\ d_1$
$s_2\ t_2\ d_2$
$\vdots$
$s_m\ t_m\ d_m$

出力

都市 $1$ から都市 $n$ に到達可能な体重 $w$ の最大値及び、$w$ が最大値の時都市 $1$ から都市 $n$ に到達するために通る必要のある道の数の最小値を、空白区切り で出力してください。 最後に改行してください。

サンプル

3 3
1 3 2
1 2 3
2 3 4

3 2

3 4
1 3 999999999
1 2 999999999
2 3 999999999
1 3 999999998

999999999 1