5. Оптимальный плейлист

Анна $-$ обычный пользователь интернета. Анна очень любит слушать музыку и пользоваться сервисом Яндекс.Музыка. Однажды, слушая песни на Яндекс.Музыке в режиме случайного перемешивания, Анна была очень расстроена тем, что после её любимой группы «‎Эпидемия» внезапно заиграл Григорий Лепс. Пылающая от негодования Анна написала гневное письмо в техническую поддержку сервиса, после чего команда разработчиков Яндекс.Музыки решила улучшить выбор следующей песни для проигрывания.

Всего на сервисе находится $N$ песен, каждую из которых Анна хочет послушать хотя бы один раз. При этом Анна не возражает против повторного прослушивания песен, однако очень возражает против резкой смены жанров. В базе данных Яндекс.Музыки помимо самой музыки содержится информация о том, насколько некоторые песни похожи по жанру друг на друга. Каждая запись имеет вид $(a, b, U)$ и означает, что если включить песню с номером $b$ сразу после песни с номером $a$, пользователь испытает $U$ единиц недовольства.

Имея такие данные, Яндекс.Музыка должна составить оптимальный для пользователя плейлист, удовлетворяющий следующим условиям:

• Каждая песня содержится в нём хотя бы один раз;
• Для каждой пары соседних песен имеется соответствующая запись в базе данных (лучше не переключать песни, не зная, чем это может обернуться);
• Максимальное недовольство, которое пользователь испытает от переключения песен в процессе прослушивания, должно быть как можно меньше.

Сможете ли вы составить плейлист, удовлетворяющий указанным условиям?

В первой строке входного файла содержатся два целых числа $N$ и $M$ ($1 \le N \le 10^5$, $1 \le M \le 2 \times 10^5$), разделённые пробелами: количество песен, которые хочет прослушать Анна, и количество записей о переходах между этими песнями, соответственно.

Следующие $M$ строк содержат по три целых числа $a_i$, $b_i$, $U_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le U_i \le 10^9$), разделённых пробелами, которые говорят о том, что, если включить песню с номером $b_i$ сразу после песни с номером $a_i$, пользователь испытает $U_i$ единиц недовольства. Гарантируется, что никакой переход от одной песни к другой не встречается в записях дважды.

Выведите единственное число: максимальное недовольство, которое испытает Анна в процессе прослушивания оптимально составленного плейлиста, или -1, если плейлист составить невозможно.