Задача "Грузовик"

Задана карта автодорог. Каждая дорога соединяет два города, и для нее известен максимальный вес грузовика, который может по ней проехать.

Необходимо определить, грузовик какого максимального веса может проехать из горда s в город t.

Формат входного файла

Первая строка входного файла содержит четыре целых числа: количество городов n (2≤n≤1000), количество дорог m (0≤m≤100000), номер начального города s и номер конечного города t (1≤s,t≤n, s<>t).

Каждая из последующих m строк описывает одну дорогу. Описание дороги состоит из трех чисел - номеров u и v (1≤u,v≤n, u<>v) двух городов, которые эта дорога соединяет, и максимального веса w (0<w≤10⁹) грузовика, который может проехать по этой дороге.

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

Формат выходного файла

Если из города s невозможно доехать в город t, выведите в выходной файл фразу No path!.

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

Пример

3 3 1 3
1 2 15
2 3 15
1 3 10

15
3
1 2 3

2 0 1 2

No path!