ЛКШата збираються на екскурсію у Яремче. Яремче --- гарне місто у Карпатах, в якому площі з'єднуються одна з одною короткими вулицями, кожну з яких можна пройти не більш як за десять хвилин(ми так придумали). ЛКШата хочуть скласти цікавий маршрут екскурсії. Оскільки вони поїдуть автобусами, то маршрут екскурсії повинен починатися і закінчуватися однією і тією ж площею. На жаль, у ЛКШат буде дуже мало часу. Тому вони вирішили обрати найбільш короткий кільцевий маршрут, що не проходить ні по якій вулиці двічі.

Допоможіть ЛКШатам знайти такий маршрут.

Формат вхідних даних

Перший рядок вхідного файлу містить два натуральні числа \(n\) і \(m\) --- кількість площ та вулиць у Яремче (\(1 \le n \le 1\,000\), \(1 \le m \le 10\,000\)). Площі пронумеровані від \(1\) до \(n\).

Наступні \(m\) рядків містять опис вулиць. Кожна вулиця описується трьома цілими числами --- номерами площ, які вона з'єднує, та кількістю хвилин, які потрібні ЛКШ-атам на те, щоб пройти нею (від однієї до десяти хвилин). Між двома площами може бути більше однієї вулиці. Вулиця зʼєднує дві різні площі.

Гарантується, що у місті існує щонайменше один кільцевий маршрут.

Формат вихідних даних

Перший рядок вихідного файлу повинен містити одне число --- тривалість мінімального маршруту у хвилинах.

Приклад вхідних даних

5 6
1 2 1
2 3 10
1 3 1
2 4 1
3 4 1
1 5 1

Приклад вихідних даних

4