На руке у капитана Джека Воробья красуется чёрная метка, и он избегает выхода в открытое море, потому что там его поджидает морское чудище Кракен. Но свободолюбивая натура пирата не позволяет ему усидеть на одном месте. И вот Джек собирается на Тортугу.

В Карибском море есть n островов. Джек собирается добираться до Тортуги, переправляясь с острова на остров по маршрутам, которые позволяют выходить в открытое море только на небольшие промежутки времени. Для некоторых пар островов Джеку известны такие маршруты, но они всё равно могут представлять опасность — на каждом таком маршруте есть некоторая вероятность встретить Кракена.

Джек очень торопится и хочет добраться до Тортуги, посетив при этом минимально возможное количество островов. Если таких путей несколько, то он хочет следовать тем из них, на котором вероятность встречи с Кракеном минимальна. Но Джека устроит любой путь, проходящий через наименьшее количество островов, на котором вероятность встретить Кракена отличается от оптимальной не более чем на 10⁻⁶. Помогите Джеку найти такой путь.

В первой строке даны два целых числа n и m — количество островов и известных маршрутов между ними соответственно (2 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁵). Во второй строке находятся два целых числа s и t — номер острова, на котором находится Джек, и номер Тортуги (1 ≤ s, t ≤ n; s ≠ t). В каждой из следующих m строк записано по три целых числа — номера островов a_i и b_i, между которыми известен маршрут, и p_i — вероятность встретить Кракена на этом маршруте в процентах (1 ≤ a_i, b_i ≤ n; a_i ≠ b_i; 0 ≤ p_i ≤ 99). Между каждой парой островов известно не более одного маршрута. Гарантируется, что от острова, на котором находится Джек, до Тортуги существует хотя бы один путь по известным маршрутам.

В первой строке выведите через пробел числа k и p — количество островов в пути и вероятность встретить Кракена на этом пути. p должно быть выведено с абсолютной погрешностью не более 10⁻⁶. В следующей строке следует вывести k чисел, разделённых пробелами — номера островов в порядке следования. Если существует несколько решений, то выведите любой из них.