Каждое утро Фермер Джон идет от дома к амбару. Ферма представляет собой множество из N полей (1 <= N <= 100) (дом на поле 1, амбар на поле N), соединенных M (1 <= M <= 10,000) двунаправленными дорогами, с каждой из которых ассоциирована длина.
Никакие два поля не соединены более чем одной дорогой, и существует маршрут дорог от любого поля к любому. Когда ФД идет от одного поля к другому, он всегда выбирает маршрут, состоящий из последовательности дорог, которые дают минимальную суммарную длину.
Коровы решили сделать ФД маленькую неприятность, выложив сено на одной из M дорог, тем самым удваивая ее длину.
Коровы хотят выбрать такую дорожку, чтобы максимально увеличить расстояние, которое ФД пройдет от дома до амбара. Помогите коровам определить, насколько они удлинят маршрут ФД.
PROBLEM NAME: rblock
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N (1 <= N <= 100) и M (1 <= M <= 10,000).
* Строки 2..1+M: Строка j+1 описывает j-ую двунаправленную дорожку тремя разделенными пробелами целыми числами Aj Bj Lj, где Aj и Bj это числа от 1 до N, указывающие поля, соединенные этой Дорогой, а Lj - длина этой дороги (в диапазоне 1...1,000,000).
Формат выходных данных
* Строка 1: Максимально возможное увеличение общей длины кратчайшего маршрута, которого можно добиться удвоением длины одной дороги.
Примечание
Если коровы удвоят длину дороги от поля 3 к полю 4 (от 3 до 6), тогда кратчайшим маршрутом станет путь 1-3-5, с общей длиной 1+7= 8. Что на 2 больше, чем исходный кратчайший маршрут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
|
2
|