Почти кратчайший путь - взвешенный

Поиск кратчайшего пути от начальной точки до конечной, с заданным набором точек и длинами ребер их соединяющих, — уже хорошо известная задача. Это уже часть нашей повседневной жизни, поскольку программы поиска кратчайшего пути широко используются в наше время.

Большинству людей эти приложения нравятся, поскольку они сильно облегчают их жизнь. А может и не сильно.

Сейчас, когда почти каждый имеет доступ к устройствам GPS-навигации, способным рассчитывать кратчайшие пути, большинство маршрутов, образующих кратчайший путь, становятся медленнее из-за интенсивного движения. Поскольку большинство людей пытается следовать по одному и тому же пути, больше не стоит следовать этим указаниям.

Имея это в виду, Ваш начальник просит Вас разработать новое приложение, доступ к которому будет иметь только он. Это сэкономит ему время на встрече или каком-либо срочном мероприятии. Программа должна находить не кратчайший путь, а почти кратчайший путь. Почти кратчайший путь — это такой кратчайший путь от начальной точки до конечной, что ни одно его ребро не принадлежит какому-либо кратчайшему пути между начальной и конечной точками.

На рисунке ниже представлена карта с кругами — точками местоположения, и стрелками — односторонними маршрутами с указанными длинами. Начальная точка отмечена как $s$, а конечная точка отмечена как $d$. Жирные линии относятся к кратчайшему пути (в данном случае имеются два кратчайших пути, каждый с суммарной длиной $4$). Почти кратчайший путь обозначен пунктирными линиями (суммарная длина $5$), поскольку ни один маршрут между двумя последовательными точками не принадлежит ни одному кратчайшему пути. Обратите внимание, что может существовать более одного возможного ответа, например, если маршрут длиной $3$ имеет длину $1$. Ответ даже может не существовать.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа $n(2\le n\le 500)$ и $m(1\le m\le 10^4)$, обозначающие соответственно количество точек на карте и количество существующих односторонних маршрутов, соединяющих две точки. Каждая точка обозначается целым числом от $0$ до $n-1$. Вторая строка содержит два целых числа $s$ и $d$, обозначающих соответственно начальную и конечную точки $(s\ne d;0\le s,d<n)$.

Каждая из следующих $m$ строк содержит три целых числа $u,v$ и $p(u\ne v,0\le u,v<n,1\le p\le 10^3)$, указывающих на существование одностороннего маршрута из $u$ в $v$ с расстоянием $p$. Существует не более одного маршрута от точки $u$ до точки $v$, но обратите внимание, что существование маршрута от $u$ до $v$ не означает, что существует маршрут от $v$ до $u$, и, если такая дорога существует, она может иметь другую длину. Последняя строка содержит два нуля и не обрабатывается.

Выходные данные

Для каждого теста выведите одну строку, содержащую $-1$, если невозможно соответствовать требованиям, или целое число, представляющее длину найденного почти кратчайшего пути.

Примеры