Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
Вася — зелёный тролль 80-го уровня с большой секирой — достаточно занятой персонаж, и он не хочет терять время и силы на зачистку локаций. К счастью, есть и другой способ добраться до Золотых Штанов — внести немного реальных денег, после чего некоторые переходы между локациями станут открытыми!
Мир Rawcraft содержит N локаций; Вася находится в локации 1, Золотые Штаны — в локации N. Некоторые локации соединены переходами, по которым можно перемещаться в обоих направлениях. j-й переход открывается за внесение доната Pj: если Вася внёс сумму P, то все переходы с Pj <= P становятся для него открытыми.
Вася хочет добраться до Золотых Штанов как можно быстрее. Помогите ему определить минимальную сумму доната, необходимую для построения пути.
Входные данные
Первая строка содержит целые числа N и M (1 <= N <= 100, 0 <= M <= 10^4) — количества локаций и переходов.
Следующие M строк описывают переходы. Каждая из них содержит целые числа Aj, Bj и Pj (1 <= Aj, Bj <= N, 0 <= Pj <= 10^9) — номера локаций, между которыми возможен переход, и сумма доната, требуемая для его открытия.
Выходные данные
Выведите одно целое число — минимальное количество денег, которое нужно внести, чтобы дойти из локации 1 в локацию N. Если Вася не сможет получить Золотые Штаны, выведите -1.
Примеры
| Входные данные | Выходные данные |
4 3
1 2 5
2 3 10
3 4 8 | 10 |
4 4
1 2 10
1 3 10
2 4 15
3 4 20 | 15 |
4 2
1 2 0
3 4 5 | -1 |
Для отправки решений необходимо выполнить вход.
|