Почти найкоротший шлях - зважений

Пошук найкоротшого шляху від початкової точки до кінцевої, з урахуванням заданого набору точок і довжин ребер, що їх з'єднують, — це вже добре відома задача. Вона стала частиною нашого повсякденного життя, оскільки програми для пошуку найкоротшого шляху широко використовуються сьогодні.

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

Зараз, коли майже кожен має доступ до пристроїв 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$, якщо неможливо відповідати вимогам, або ціле число, що представляє довжину знайденого майже найкоротшого шляху.

Приклади