Михаил Адриансзон де Рюйтер - наиболее известный адмирал в истории Дании, хорошо известный в англо-датской войне 17 века. Де Рюйтер лично командовал флагманом и давал команды союзным военным кораблям во время морских сражений.

Во времена де Рюйтера теория графов как раз только появлялась, и адмирал использовал все ее преимущества при планировании морских сражений. Путевые точки в море отображаются вершинами, возможные переходы между ними представляются направленными ребрами. Для любых двух путевых точек W1 и W2 существует не более одного перехода W1 → W2. На каждом ориентированном ребре записано количество пушечных ядер, которое следует выпустить для безопасного провода корабля по соответствующему переходу, потопив корабли противника на пути.

Одной из наиболее удачных тактик де Рюйтера был маневр де Рюйтера. Два военных корабля выходили из одной точки, разделялись и пробивались сквозь вражеский флот, соединяясь в пункте назначения. Маневр подразумевает движение двух кораблей по двум различным маршрутам, которые не пересекаются ни в путевых точках (кроме начальной и конечной), ни по одному из переходов во время сражения.

Будучи датчанином, адмирал де Рюйтер не любил тратить деньги; в морской войне 17 века это означало использовать как можно меньше дорогих пушечных ядер.

Конкретный пример тактики де Рюйтера, визуализированной в виде графа. Два корабля (‘красный’ и ‘синий’) движутся из общей начальной точки (1) к общей конечной точке (6). Путь красного корабля 1 → 3 → 6 (по пути следует выстрелить 33 ядра); путь синего корабля 1 → 2 → 5 → 4 → 6 (по пути следует выстрелить 53 ядра). Всего при маневре следует выпустить 86 ядер. Кроме начальной и конечной точки никакая вершина и никакое ребро не посещены обоими кораблями.

Входные данные

Каждый тест состоит из:

• строки из двух целых чисел v (3 ≤ v ≤ 1000) и e (3 ≤ e ≤ 10000) - количества путевых точек и переходов.

• далее следуют e строк: для каждого перехода строка содержит три целых числа:

• ai (1 ≤ ai ≤ v) - начальная точка перехода;

• bi (1 ≤ bi ≤ v) и (ai ≠ bi) - конечная точка перехода. Все переходы являются направленными;
• ci (1 ≤ ci ≤ 100) - количество пушечных ядер, которое должно быть выпущено при движении по переходу.

Начальная точка движения 1, конечная точка v. Всегда существует как минимум два различных пути между точками 1 и v.

Выходные данные

Для каждого теста вывести наименьшее общее количество ядер, которое следует использовать для того чтобы оба корабля добрались до конечной точки маневра.