Квіткові стежки#7913
Щоб залучити більше відвідувачів, керівник національного парку вирішив посадити квіти по обидва боки популярних стежок, якими ходять відвідувачі. Відвідувачі йдуть від входу в парк до найвищої вершини по найкоротшій стежці. Тому він хоче дізнатися, скільки метрів квітів потрібно для реалізації його ідеї.
Наприклад, у парку, карта якого зображена на рисунку, відвідувачі слідують лише одним із трьох наступних шляхів (які є найкоротшими шляхами від входу до найвищої вершини).
На вході деякі відвідувачі обирають крайню праву стежку, щоб дістатися до пам'ятки (через метрів), потім йдуть прямо до точки метрів), а далі обирають пряму стежку до найвищої вершини ( метрів).
Інші відвідувачі повертають наліво на вході і досягають точки (через метрів). Потім вони обирають одну з двох стежок, що ведуть до точки (обидві мають метрів). У точці вони йдуть по прямій стежці до найвищої вершини ( метрів).
Зверніть увагу, що популярні маршрути (тобто маршрути, якими йдуть відвідувачі) виділені жовтим кольором. Оскільки загальна довжина цих маршрутів становить метрів, то довжина квітів, необхідних для покриття обох боків популярних стежок, становить метрів (3860 = 2 \cdot 1930).
Виходячи з опису парку з його пам'ятками та (двосторонніми) стежками, визначте, скільки квітів потрібно для покриття обох боків популярних маршрутів. Гарантується, що для заданих вхідних даних завжди існує шлях від входу в парк до найвищої вершини.
Перший рядок містить два цілих числа: p~(2 \le p \le 10000) і t~(1 \le t \le 250000). Тут — кількість пам'яток, — кількість стежок. Точки позначаються цілими числами від до p - 1. Точка входу — , а найвищий пік — точка p - 1.
Кожен з наступних рядків описує одну стежку. Він містить три цілі числа: p_1, p_2 і l~(1 \le l \le 1000), які вказують, що (двостороння) стежка безпосередньо з'єднує p_1 і p_2 (не обов'язково різні) і має довжину (в метрах).
Виведіть довжину квітів (в метрах), необхідних для покриття обох боків популярних стежок.
Приклад 1
Приклад 2