Банкополис — удивительный город, в котором все n перекрестков расположены на одной прямой, пронумерованы вдоль нее от 1 до n, и на углу каждого из них есть офис банка.
Перекрестки соединены m ориентированными велосипедными дорожками (дорожка номер i ведет от перекрестка ui к перекрестку vi), для каждой дорожки известна сложность проезда по ней.
Обычный клиент банка Олег на день рождения этого самого банка решил подарить счастье и радость его работникам. Он хочет посетить ровно k отделений банка и в каждом посещенном отделении подарить всем его работникам подарки.
Проблема в том, что Олег не хочет видеть реакцию на свои подарки, поэтому он не будет пользоваться дорожкой, проходящей мимо офиса, в котором он уже раздавал подарки (формально, дорожка номер i проходит мимо офиса на перекрестке x если и только если min(ui, vi) < x < max(ui, vi))). Конечно, в каждом офисе Олег может раздавать подарки только один раз. Передвигаться Олег будет по дорожкам, причем он хочет использовать ровно k - 1 дорожку на перемещение между офисами. Олег может начать с любого офиса и закончить поздравлять в любом офисе.
Олег хочет выбрать среди всех возможных маршрутов тот, суммарная сложность дорожек в котором минимальна. Помогите ему найти эту наименьшую возможную сложность.
Выходные данные
В единственной строке выведите минимальную суммарную сложность дорожек в маршруте, или -1, если нет подходящих Олегу маршрутов.
Примечание
В первом примере Олег посещает банки по маршруту 1 → 6 → 2 → 4.
Маршрут 1 → 6 → 2 → 7 с меньшей сложностью является некорректным потому что дорожка 2 → 7 проходит мимо офиса 6 в котором Олег уже побывал.
Во втором примере Олег посещает банки по маршруту 4 → 1 → 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 4
4
1 6 2
6 2 2
2 4 2
2 7 1
|
6
|
|
2
|
4 3
4
2 1 2
1 3 2
3 4 2
4 1 1
|
3
|