Задачи
Цветочные тропы
Цветочные тропы
Чтобы привлечь больше посетителей, управляющему национальным парком пришла в голову идея посадить цветы по обеим сторонам популярных троп, по которым ходят обычные люди. Обычные люди идут только от входа в парк на самую высокую вершину, откуда захватывает дух, по кратчайшей тропе. Итак, он хочет знать, сколько необходимо метров цветов для реализации его идеи.
Например, в парке, карта которого изображена на рисунке, простые люди следуют только одной из трех следующих путей (которые являются кратчайшими путями от входа на самую высокую вершину).
\begin{itemize}
\item При входе некоторые посетители стартуют по крайней правой тропе, чтобы добраться до достопримечательности $3$ (через $100$ метров), следуют прямо до точки $7~(200$ метров), а затем выбирают прямую тропу на самую высокую вершину ($620$ метров).
\item Остальные следуют налево при входе и достигают точки $1$ (через $580$ метров). Затем выбирают одну из двух троп, ведущих к точке $4$ (обе имеют $90$ метров). В точке $4$ они идут по прямой тропе на самую высокую вершину ($250$ метров).
\end{itemize}
\includegraphics{https://static.e-olymp.com/content/0b/0b42fd3a63b431eeb30fe6739fcc5126cc9bd169.gif}
Обратите внимание, что популярные маршруты (то есть маршруты, по которым идут обычные люди) выделены желтым цветом. Поскольку сумма их длин составляет $1930$ метров, то длина цветов, необходимых для покрытия обеих сторон популярных троп, составляет $3860$ метров $(3860 = 2 \cdot 1930)$.
По описанию парка с его достопримечательностями и (двусторонними) тропами выясните, сколько цветов необходимо для покрытия обеих сторон популярных маршрутов. Гарантируется, что для заданных входных данных всегда существует некоторый путь от входа в парк до самой высокой вершины.
\InputFile
Первая строка содержит два целых числа: $p~(2 \le p \le 10000)$ и $t~(1 \le t \le 250000)$. Здесь $p$ --- количество достопримечательностей, $t$ --- количество троп. Точки обозначаются целыми числами от $0$ до $p - 1$. Точка входа $0$, а самый высокий пик --- точка $p - 1$.
Каждая из следующих $t$ строк описывает одну тропу. Она содержит три целых числа: $p_1, p_2$ и $l~(1 \le l \le 1000)$, которые указывают, что (двусторонняя) тропа напрямую соединяет $p_1$ и $p_2$ (не обязательно разные) и имеет длину $l$ (в метрах).
\OutputFile
Выведите длину цветов (в метрах), необходимых для покрытия обеих сторон популярных троп.
Входные данные #1
10 15 0 1 580 1 4 90 1 4 90 4 9 250 4 2 510 2 7 600 7 3 200 3 3 380 3 0 150 0 3 100 7 8 500 7 9 620 9 6 510 6 5 145 5 9 160
Выходные данные #1
3860
Входные данные #2
4 7 0 1 1 0 2 2 0 3 10 0 3 3 1 3 2 2 3 1 1 1 1
Выходные данные #2
18