Input file name: flow.in

Output file name: flow.out

Time limit: 2 s, Memory limit: 64 MB

Задан ориентированный граф с M вершинами и N рёбрами. Для каждого ребра задана его пропускная способность Cj (1 ≤ j ≤ N). Среди вершин выделены источник и сток.

Требуется определить максимальный поток из источника в сток.

Input

Первая строка входного файла содержит величины M и N (2 ≤ M ≤ 1000, 1 ≤ N ≤ 10000). Во второй строке файла записаны значения s и t – номера источника и стока соответственно (1 ≤ s, t ≤ M, s ≠ t). Каждая из последующих N строк описывает одно ребро и содержит три числа: номер начальной и конечной вершины, а также пропускную способность этого ребра. Величины Cj — целые, положительные, не превосходящие 100. Нумерация вершин начинается с единицы.

Output

Выведите в первой строке величину потока, поступающего в сток, а в последующих N строках — поток, проходящий по каждому ребру. Порядок задания величин потока должен соответствовать порядку описания рёбер во входном файле. Если задача допускает несколько решений, выведите любое из них.