1961. Путь

Имеется телекоммуникационная сеть, состоящая из `N` узлов. Некоторые пары узлов соединены каналами связи, для каждого канала известна его пропускная способность в обоих направлениях. Требуется найти путь для передачи трафика между двумя заданными узлами, имеющий максимальную пропускную способность. Пропускная способность пути равняется минимальной пропускной способности среди всех каналов (в соответствующем направлении), через которые он проходит.

В первой строке входного файла записаны через пробел четыре целых числа — `N`, `M`, `a` и `b` (`2\ ≤\ N\ ≤\ 1000`, `0\ ≤\ M\ ≤\ 10\ 000`, `1\ ≤\ a,\ b\ ≤\ N`, `a\ ≠\ b`). Здесь `N` — количество узлов, `M` — количество каналов связи, `a` и `b` — номера начального и конечного узла.

В каждой из следующих `M` строк записано по 4 разделенных пробелами целых числа `u`, `v`, `c1`, `c2` (`1\ ≤\ u\ <\ v\ ≤\ N`, `1\ ≤\ c1,\ c2\ ≤\ 1\ 000\ 000`), где узлы `u` и `v` — концы очередного канала связи, `c1` — пропускная способность в направлении от `u` к `v`, `c2` — пропускная способность в направлении от `v` к `u`. Любые два узла соединены не более чем одним каналом.

В первой строке выходного файла выведите одно целое число — пропускную способность наилучшего пути. Если пути от `a` к `b` не существует, выведите 0. Если же путь существует, выведите в следующей строке через пробел номера узлов в порядке следования (первым узлом должен быть `a`, последним — `b`). Если подходящих путей несколько, то выведите путь с наименьшим количеством рёбер (каналов). Если таких путей также окажется больше одного, то выведите любой.

4 5 1 2
1 3 20 30
3 4 100 50
2 3 20 15
1 2 5 20
2 4 10 10

15
1 3 2

Примечание. На рисунке далее приведён граф сети для данного примера (число на ребре рядом с каждой вершиной показывает пропускную способность канала в направлении от неё).