В скромном акте встречи радость раскрывается, как цветок в цветении.
Отсутствие заставляет сердце тосковать. Мариан продала свой последний товар на рынке в то же время, когда Робин закончил тренировку у Великого Дуба. Они не могли дождаться встречи, поэтому оба отправились в путь без промедления.
Сеть путешествий представлена как \(n\) вершин, пронумерованных от \(1\) до \(n\), и \(m\) рёбер. \(i\)-е ребро соединяет вершины \(v_i\) и \(u_i\) и занимает \(w_i\) секунд на преодоление (все \(w_i\) четные). Мариан начинает с вершины \(1\) (Рынок), а Робин начинает с вершины \(n\) (Великий Дуб).
Кроме того, у \(h\) из \(n\) вершин есть по одному доступному коню. И Мариан, и Робин являются опытными всадниками и могут оседлать лошадей в считанные секунды (т.е. за \(0\) секунд). Время в пути сокращается вдвое при езде на лошади. Как только они сядут на лошадь, она будет служить им на протяжении всего оставшегося пути. Встреча должна происходить на вершине (т.е. не на ребре). Каждый из них также может останавливаться в вершинах.
Выведите самое раннее время, когда Робин и Мариан могут встретиться. Если вершины \(1\) и \(n\) не соединены, выведите \(-1\), так как встреча отменяется.
Выходные данные
Для каждого набора входных данных выведите одно целое число — самое раннее время, когда Робин и Мариан могут встретиться. Если встреча невозможна, выведите \(-1\).
Примечание
В первом наборе входных данных Мариан едет от вершины \(1\) к вершине \(2\), Робин ждет.
Во втором наборе входных данных вершины \(1\) и \(3\) не соединены.
В третьем наборе входных данных и Мариан, и Робин едут к вершине \(2\), чтобы встретиться.
В четвертом наборе входных данных Мариан едет к вершине \(2\) без лошади, оседлает лошадь на вершине \(2\) и едет к вершине \(3\), чтобы встретиться с Робином.
В пятом наборе входных данных Мариан едет к вершине \(2\) без лошади, оседлает лошадь на вершине \(2\) и возвращается к вершине \(1\), а затем к вершине \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 1 1
1
1 2 10
3 1 2
2 3
1 2 10
3 3 1
2
1 2 4
1 3 10
2 3 6
4 3 2
2 3
1 2 10
2 3 18
3 4 16
3 2 1
2
1 2 4
1 3 16
7 7 1
3
1 5 2
2 6 12
1 2 12
6 4 8
7 3 4
6 3 4
7 6 4
|
5
-1
6
19
14
12
|