Чтобы привлечь больше посетителей, управляющему национальным парком пришла в голову идея посадить цветы по обеим сторонам популярных троп, по которым ходят обычные люди. Обычные люди идут только от входа в парк на самую высокую вершину, откуда захватывает дух, по кратчайшей тропе. Итак, он хочет знать, сколько необходимо метров цветов для реализации его идеи. Например, в парке, карта которого изображена на рисунке, простые люди следуют только одной из трех следующих путей (которые являются кратчайшими путями от входа на самую высокую вершину). \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 Выведите длину цветов (в метрах), необходимых для покрытия обеих сторон популярных троп.