G. Shaharlar yo‘li

Mamlakatda N ta shahar va M ta ikki tomonlama yo‘l bor. i-yo‘l uᵢ va vᵢ shaharlarni bog‘laydi, undan o‘tish wᵢ daqiqa davom etadi.

Olimpiada ishtirokchisi 1-shahar (Toshkent)dan N-shaharga eng tez yetib bormoqchi. Eng qisqa vaqtni va shu vaqtga ega turli yo‘nalishlar sonini toping. Yo‘nalishlar soni katta bo‘lishi mumkin, shuning uchun uni 10⁹ + 7 ga bo‘lgandagi qoldiqni chiqaring.

Ikki yo‘nalish turli hisoblanadi, agar ular o‘tadigan yo‘llar ketma-ketligi farq qilsa (ikki shahar orasidagi ikki xil yo‘l — ikki xil yo‘nalish).

Kirish ma’lumotlari

Birinchi qatorda N va M. Keyingi M ta qatorning har birida uchta son: uᵢ vᵢ wᵢ. Ikki shahar orasida bir nechta yo‘l bo‘lishi mumkin.

Chiqish ma’lumotlari

Agar N-shaharga yetib bo‘lmasa, -1. Aks holda bitta qatorda ikkita son: eng qisqa vaqt va shunday yo‘nalishlar soni (10⁹ + 7 bo‘yicha qoldiq).

Cheklovlar

• 2 ≤ N ≤ 10⁵
• 0 ≤ M ≤ 2 · 10⁵
• 1 ≤ uᵢ, vᵢ ≤ N, uᵢ ≠ vᵢ
• 1 ≤ wᵢ ≤ 10⁹
• Vaqt 10¹⁴ gacha: C++ da long long ishlating.

1-misol (rasmda): 1 → 2 → 3 → 4 → 5, 1 → 3 → 4 → 5 va 1 → 2 → 4 → 5 — har biri 10 daqiqa. Rasmda har shahar yonida «eng qisqa vaqt · shunday yo‘llar soni» yozilgan.

2-misol: 4-shaharga 1-shahardan yo‘l yo‘q.