Адмірал#4022

Адмірал

1 секунда

64 мегабайти

Легка

Міхаїл Адріансзон де Рюйтер — найвідоміший адмірал в історії Нідерландів, відзначився в англо-голландських війнах $17$ століття. Де Рюйтер особисто командував флагманом і керував союзними військовими кораблями під час морських битв.

У часи де Рюйтера теорія графів тільки починала розвиватися, і адмірал використовував її переваги для планування морських битв. Точки маршруту в морі зображуються вершинами, а можливі переходи між ними — напрямленими ребрами. Для будь-яких двох точок маршруту $W_{1}$ W_1 і $W_{2}$ W_2 існує не більше одного переходу $W_{1} \to W_{2}$ W_1 \to W_2. На кожному орієнтованому ребрі вказано кількість гарматних ядер, яку потрібно випустити для безпечного проходження корабля, потопивши ворожі судна на шляху.

Однією з найуспішніших тактик де Рюйтера був маневр де Рюйтера. Два військові кораблі виходять з однієї точки, розділяються і пробиваються крізь ворожий флот, з'єднуючись у пункті призначення. Маневр передбачає рух двох кораблів по двох різних маршрутах, які не перетинаються ні в точках маршруту (крім початкової та кінцевої), ні по жодному з переходів під час битви.

Будучи голландцем, адмірал де Рюйтер не любив витрачати гроші; у морській війні $17$ століття це означало використовувати якомога менше дорогих гарматних ядер.

Конкретний приклад тактики де Рюйтера, візуалізованої у вигляді графа. Два кораблі ('червоний' і 'синій') рухаються з загальної початкової точки ( $1$ ) до загальної кінцевої точки ( $6$ ). Шлях червоного корабля $1 \to 3 \to 6$ 1 \to 3 \to 6 (по шляху слід випустити $33$ ядра); шлях синього корабля $1 \to 2 \to 5 \to 4 \to 6$ 1 \to 2 \to 5 \to 4 \to 6 (по шляху слід випустити $53$ ядра). Всього при маневрі слід випустити $86$ ядер. Крім початкової і кінцевої точки жодна вершина і жодне ребро не відвідані обома кораблями.

Вхідні дані

Кожен тест складається з:

рядка з двох цілих чисел $v$ ( $3 \leq v \leq 1000$ 3 \leq v \leq 1000) і $e$ ( $3 \leq e \leq 10000$ 3 \leq e \leq 10000) — кількості точок маршруту і переходів;
далі слідують $e$ рядків: для кожного переходу рядок містить три цілі числа:
- $a_{i}$ a_i ( $1 \leq a_{i} \leq v$ 1 \leq a_i \leq v) — початкова точка переходу;
- $b_{i}$ b_i ( $1 \leq b_{i} \leq v$ 1 \leq b_i \leq v, $a_{i} \neq = b_{i}$ a_i \ne b_i) — кінцева точка переходу. Всі переходи є напрямленими;
- $c_{i}$ c_i ( $1 \leq c_{i} \leq 100$ 1 \leq c_i \leq 100) — кількість гарматних ядер, яку потрібно випустити при русі по переходу.

Початкова точка руху — $1$ , кінцева точка — $v$ . Завжди існує як мінімум два різних шляхи між точками $1$ і $v$ .

Вихідні дані

Для кожного тесту вивести найменшу загальну кількість ядер, яку слід використати для того, щоб обидва кораблі дісталися до кінцевої точки маневру.

Приклади

Приклад 1