Чтобы привлечь больше посетителей, управляющему национальным парком пришла в голову идея посадить цветы по обеим сторонам популярных троп, по которым ходят обычные люди. Обычные люди идут только от входа в парк на самую высокую вершину, откуда захватывает дух, по кратчайшей тропе. Итак, он хочет знать, сколько необходимо метров цветов для реализации его идеи.
Например, в парке, карта которого изображена на рисунке, простые люди следуют только одной из трех следующих путей (которые являются кратчайшими путями от входа на самую высокую вершину).
При входе некоторые посетители стартуют по крайней правой тропе, чтобы добраться до достопримечательности (через метров), следуют прямо до точки метров), а затем выбирают прямую тропу на самую высокую вершину ( метров).
Остальные следуют налево при входе и достигают точки (через метров). Затем выбирают одну из двух троп, ведущих к точке (обе имеют метров). В точке они идут по прямой тропе на самую высокую вершину ( метров).
Обратите внимание, что популярные маршруты (то есть маршруты, по которым идут обычные люди) выделены желтым цветом. Поскольку сумма их длин составляет метров, то длина цветов, необходимых для покрытия обеих сторон популярных троп, составляет метров .
По описанию парка с его достопримечательностями и (двусторонними) тропами выясните, сколько цветов необходимо для покрытия обеих сторон популярных маршрутов. Гарантируется, что для заданных входных данных всегда существует некоторый путь от входа в парк до самой высокой вершины.
Первая строка содержит два целых числа: и . Здесь — количество достопримечательностей, — количество троп. Точки обозначаются целыми числами от до . Точка входа , а самый высокий пик — точка .
Каждая из следующих строк описывает одну тропу. Она содержит три целых числа: и , которые указывают, что (двусторонняя) тропа напрямую соединяет и (не обязательно разные) и имеет длину (в метрах).
Выведите длину цветов (в метрах), необходимых для покрытия обеих сторон популярных троп.