G. Eng qisqa yo‘llar

Mamlakatda n ta shahar va ularni tutashtiruvchi m ta ikki tomonlama avtomobil yo‘li bor. Har bir yo‘lning uzunligi w km. Sayyoh 1-shahardan (Samarqand) n-shaharga (Toshkent) borishi kerak.

Sayyoh eng qisqa masofani bilmoqchi, shuningdek unga nechta turli eng qisqa yo‘l borligi ham qiziq. Ikki yo‘l turli hisoblanadi, agar ular bosib o‘tadigan shaharlar ketma-ketligi farq qilsa. Yo‘llar soni juda katta bo‘lishi mumkin, shuning uchun uni 10⁹ + 7 ga bo‘lgandagi qoldig‘ini chiqaring.

Kirish ma’lumotlari

Birinchi qatorda n va m.
Keyingi m ta qatorning har birida uchta butun son u v w — u va v shaharlar orasida uzunligi w bo‘lgan yo‘l bor.

Chiqish ma’lumotlari

Agar n-shaharga yetib borib bo‘lmasa, -1 chiqaring. Aks holda bitta qatorda ikkita son chiqaring: eng qisqa masofa va shunday uzunlikdagi yo‘llar sonining 10⁹ + 7 ga bo‘lgandagi qoldig‘i.

Cheklovlar

2 ≤ n ≤ 2·10⁴; 1 ≤ m ≤ 4·10⁴; 1 ≤ w ≤ 10⁹; u ≠ v; har bir juft shahar orasida ko‘pi bilan bitta yo‘l bor.

1–70-testlar 1 balldan, 71–80-testlar 3 balldan, jami 100 ball. 1–2-testlar — shartdagi misollar.

1-misol: eng qisqa masofa 5, unga 3 ta yo‘l bor: 1–2–5 (2 + 3), 1–3–4–5 (1 + 2 + 2), 1–2–4–5 (2 + 1 + 2). 1–3–5 yo‘li uzunligi 6 — u eng qisqa emas.

2-misol: 3-shaharga hech qanday yo‘l yo‘q — javob -1.