Павел играет в одну известную компьютерную игру. Игроку предоставлена в распоряжение целая страна, где можно свободно путешествовать, выполнять квесты и набирать опыт.
В этой стране n городов, соединенных m двусторонними дорогами различной длины так, что из каждого города можно добраться до каждого. В k из этих городов имеются порталы. В начале игры все порталы закрыты. Когда игрок посещает город, в котором есть портал, этот портал становится открытым. Из открытого портала в открытый можно, как ни странно, телепортироваться. Телепортация происходит мгновенно, что дает возможность игроку быстро перемещаться между довольно удаленными областями страны.
В начале игры Павел находится в городе с номером 1. Он хочет как можно быстрее открыть все порталы. Какое наименьшее время ему для этого потребуется?
Выходные данные
Выведите единственное число — минимальное время, которое требуется игроку, чтобы открыть все порталы.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
Во втором примере игрок должен прийти в город 2, открыть в нем портал, затем отправиться в город 3, открыть там портал, телепортироваться обратно в город 2 и, наконец, завершить свое путешествие в городе 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 1
1 3 1
2 3 1
3
1 2 3
|
2
|
|
2
|
4 3
1 2 1
2 3 5
2 4 10
3
2 3 4
|
16
|
|
3
|
4 3
1 2 1000000000
2 3 1000000000
3 4 1000000000
4
1 2 3 4
|
3000000000
|