Эле нужно отправить большой пакет данных с компьютера \(1\) на компьютер \(n\) через сеть компьютеров. В настоящее время сеть работает слишком медленно, и пакет может не успеть вовремя. К счастью, добрый волшебник протянул ей руку помощи.
Сеть может быть представлена как неориентированный связный граф с \(n\) вершинами, каждая из которых представляет компьютер. Для их соединения используются \(m\) проводов. Провод \(i\) используется для соединения компьютеров \(u_i\) и \(v_i\) и имеет вес \(w_i\). Вышеупомянутый пакет при прохождении через провод \(i\) переместится с компьютера \(u_i\) на компьютер \(v_i\) (или наоборот) ровно за \(w_i\) микросекунд. Волшебник может использовать свое заклинание произвольное количество раз. Для каждого заклинания он выберет провод с индексом \(i\), соединяющий компьютеры \(u_i\) и \(v_i\), и переподключит его, выполнив следующие действия:
- Выберет один из компьютеров, соединенный этим проводом. Без ограничения общности выберем \(v_i\).
- Выберет компьютер, который в данный момент подключен к \(v_i\) (можно выбрать \(u_i\)), назовем его \(t_i\), отсоединит провод с индексом \(i\) от \(v_i\), и соединит им \(u_i\) и \(t_i\).
Переподключение провода \(i\) займет \(w_i\) микросекунд, а вес провода после этой операции не изменится. После переподключения компьютер может иметь какой-то провод, соединяющий его с самим собой. Переподключение также может сделать граф несвязным.
Задача Элы — как можно быстрее отправить пакет данных с компьютера \(1\) на компьютер \(n\). Обратите внимание, что волшебник может использовать свое заклинание сколько угодно раз (возможно, ноль). Чтобы обеспечить бесперебойную работу сети при передаче большого пакета, все заклинания могут использоваться только до начала передачи данных с компьютера \(1\).
Какое минимальное количество времени потребуется для передачи пакета данных с компьютера \(1\) на компьютер \(n\), с учетом времени, потраченного на применение заклинаний?
Выходные данные
Для каждого набора входных данных выведите одно целое число, обозначающее наименьшее количество времени, необходимое для передачи пакета данных с компьютера \(1\) на \(n\).
Примечание
Граф в первом наборе входных данных:
Эла может попросить волшебника использовать его заклинание на проводе с индексом \(7\), который соединяет компьютеры \(2\) и \(3\). Поскольку компьютер \(8\) подключена к компьютеру \(3\), волшебник может отключить провод \(7\) от компьютера \(3\) и подключить его к компьютеру \(8\) за \(3\) микросекунды (вес провода \(3\)).
После этого пакет можно отправить с компьютера \(1\) на компьютер \(8\) за \(6\) микросекунд. Следовательно, ответ \(3 + 6 = 9\) микросекунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
8 9
1 2 3
6 4 5
3 5 6
6 1 3
7 4 4
3 8 4
2 3 3
7 8 5
4 5 2
4 5
1 2 1
2 4 1
3 4 1
3 1 1
1 3 2
8 8
4 6 92
7 1 65
6 5 43
6 7 96
4 3 74
4 8 54
7 4 99
2 5 22
|
9
2
154
|