Поиск кратчайшего пути от начальной точки до конечной, с заданным набором точек и длинами ребер их соединяющих, --- уже хорошо известная задача. Это уже часть нашей повседневной жизни, поскольку программы поиска кратчайшего пути широко используются в наше время. Большинству людей эти приложения нравятся, поскольку они сильно облегчают их жизнь. А может и не сильно. Сейчас, когда почти каждый имеет доступ к устройствам GPS-навигации, способным рассчитывать кратчайшие пути, большинство маршрутов, образующих кратчайший путь, становятся медленнее из-за интенсивного движения. Поскольку большинство людей пытается следовать по одному и тому же пути, больше не стоит следовать этим указаниям. Имея это в виду, Ваш начальник просит Вас разработать новое приложение, доступ к которому будет иметь только он. Это сэкономит ему время на встрече или каком-либо срочном мероприятии. Программа должна находить не кратчайший путь, а почти кратчайший путь. Почти кратчайший путь --- это такой кратчайший путь от начальной точки до конечной, что ни одно его ребро не принадлежит какому-либо кратчайшему пути между начальной и конечной точками. На рисунке ниже представлена карта с кругами --- точками местоположения, и стрелками --- односторонними маршрутами с указанными длинами. Начальная точка отмечена как $s$, а конечная точка отмечена как $d$. Жирные линии относятся к кратчайшему пути (в данном случае имеются два кратчайших пути, каждый с суммарной длиной $4$). Почти кратчайший путь обозначен пунктирными линиями (суммарная длина $5$), поскольку ни один маршрут между двумя последовательными точками не принадлежит ни одному кратчайшему пути. Обратите внимание, что может существовать более одного возможного ответа, например, если маршрут длиной $3$ имеет длину $1$. Ответ даже может не существовать. \includegraphics{https://static.e-olymp.com/content/8a/8a86d7a219e31222c1f5cfc9bb5fd5708173cfe9.gif} \InputFile Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа $n\:(2 \le n \le 500)$ и $m\:(1 \le m \le 10^4)$, обозначающие соответственно количество точек на карте и количество существующих односторонних маршрутов, соединяющих две точки. Каждая точка обозначается целым числом от $0$ до $n - 1$. Вторая строка содержит два целых числа $s$ и $d$, обозначающих соответственно начальную и конечную точки $(s ≠ d; 0 \le s, d < n)$. Каждая из следующих $m$ строк содержит три целых числа $u, v$ и $p\:(u ≠ v, 0 \le u, v < n, 1 \le p \le 10^3)$, указывающих на существование одностороннего маршрута из $u$ в $v$ с расстоянием $p$. Существует не более одного маршрута от точки $u$ до точки $v$, но обратите внимание, что существование маршрута от $u$ до $v$ не означает, что существует маршрут от $v$ до $u$, и, если такая дорога существует, она может иметь другую длину. Последняя строка содержит два нуля и не обрабатывается. \OutputFile Для каждого теста выведите одну строку, содержащую $-1$, если невозможно соответствовать требованиям, или целое число, представляющее длину найденного почти кратчайшего пути.