注意

書籍の版によっては、書籍内のコードが正しくない場合があります。正誤表を参照してください。

問題文

ALGO 市には N 個の交差点と M 本の道路があります。i 本目の道路は、交差点 A_i と交差点 B_i を双方向に結んでおり、長さは C_i メートルです。交差点どうしは、いくつかの道路を通って必ず行き来できることが保証されます。また、 D_i = 1 であるような道路には、木が一本植えられています。

ALGO 市の市長である次郎君は、交差点 1 と交差点 N を結ぶマラソンコースを作ろうと思いました。彼は参加者を疲れさせたくないので、合計距離をできるだけ短くしたいです。また参加者に自然を楽しんでいただきたいので、合計距離が同じ場合、コース上に植えられている木の数をより多くしたいです。どのようなマラソンコースが考えられますか。

制約

• 2 \leq N \leq 8{,}000
• 1 \leq M \leq 100{,}000
• 1 \leq C_i \leq 100
• 交差点どうしは、いくつかの道路を通って必ず行き来できることが保証される
• 1 \leq A_i < B_i \leq N
• i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
• D_i は 0 または 1 である

入力例 1

3 3
1 2 70 1
2 3 20 1
1 3 90 0

出力例 1

90 2