Problem D
Maximum Flow

Input

The first line of input contains a line with four non-negative integers, $2 \le n \le 500$, $0 \le m \le 10\, 000$, $0 \le s \le n-1$ and $0 \le t \le n-1$, separated by single spaces, where $n$ is the numbers of nodes in the graph, $m$ is the number of edges, $s$ is the source and $t$ is the sink ($s \ne t$). Nodes are numbered from $0$ to $n-1$. Then follow $m$ lines, each line consisting of three (space-separated) integers $u$, $v$ and $c$ indicating that there is an edge from $u$ to $v$ in the graph with capacity $1 \le c \le 10^{8}$.

Output

The output should begin with a line containing three integers $n$, $f$, and $m’$. $n$ is the number of nodes in the flow graph (same as in input), $f$ is the size of a maximum flow from node $s$ to node $t$ in the flow graph, and $m’$ is the number of edges used in the solution. You may assume that $f < 2^{31}$.

Then there should be $m’$ lines, each containing three integers $u$, $v$ and $x$, indicating that $x$ units of flow are transported from $u$ to $v$. $x$ must be greater than $0$ and at most as big as the capacity from $u$ to $v$. Each pair of vertices $(u, v)$ should be given at most once in the output.

4 5 0 3
0 1 10
1 2 1
1 3 1
0 2 1
2 3 10

4 3 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

2 1 0 1
0 1 100000

2 100000 1
0 1 100000

2 1 1 0
0 1 100000

2 0 0