Адмірал
Міхаїл Адріансзон де Рюйтер - найвідоміший адмірал в історії Данії, відзначився в англо-данській війні 17 століття. Де Рюйтер особисто командував флагманом і керував союзними військовими кораблями під час морських битв.
У часи де Рюйтера теорія графів тільки починала розвиватися, і адмірал використовував її переваги для планування морських битв. Точки маршруту в морі зображуються вершинами, а можливі переходи між ними - напрямленими ребрами. Для будь-яких двох точок маршруту W[1] і W[2] існує не більше одного переходу W[1] → W[2]. На кожному орієнтованому ребрі вказано кількість гарматних ядер, яке потрібно випустити для безпечного проходження корабля, потопивши ворожі судна на шляху.
Однією з найуспішніших тактик де Рюйтера був маневр де Рюйтера. Два військові кораблі виходили з однієї точки, розділялися і пробивалися крізь ворожий флот, з'єднуючись у пункті призначення. Маневр передбачає рух двох кораблів по двох різних маршрутах, які не перетинаються ні в точках маршруту (крім початкової та кінцевої), ні по жодному з переходів під час битви.
Будучи данцем, адмірал де Рюйтер не любив витрачати гроші; у морській війні 17 століття це означало використовувати якомога менше дорогих гарматних ядер.
Конкретний приклад тактики де Рюйтера, візуалізованої у вигляді графа. Два кораблі (‘червоний’ і ‘синій’) рухаються з загальної початкової точки (1) до загальної кінцевої точки (6). Шлях червоного корабля 1 → 3 → 6 (по шляху слід випустити 33 ядра); шлях синього корабля 1 → 2 → 5 → 4 → 6 (по шляху слід випустити 53 ядра). Всього при маневрі слід випустити 86 ядер. Крім початкової і кінцевої точки жодна вершина і жодне ребро не відвідані обома кораблями.
Вхідні дані
Кожен тест складається з:
рядка з двох цілих чисел v (3 ≤ v ≤ 1000) і e (3 ≤ e ≤ 10000) - кількості точок маршруту і переходів.
далі слідують e рядків: для кожного переходу рядок містить три цілі числа:
a[i](1 ≤a[i]≤ v) - початкова точка переходу;b[i](1 ≤b[i]≤ v) і (a[i]≠b[i]) - кінцева точка переходу. Всі переходи є напрямленими;c[i](1 ≤c[i]≤ 100) - кількість гарматних ядер, яке повинно бути випущено при русі по переходу.
Початкова точка руху 1, кінцева точка v. Завжди існує як мінімум два різних шляхи між точками 1 і v.
Вихідні дані
Для кожного тесту вивести найменшу загальну кількість ядер, яке слід використати для того щоб обидва кораблі дісталися до кінцевої точки маневру.