Problem C
Ice Cream
The Better Get Obese (BGO) ice cream factory is gearing up for the holiday season, and after several years with mediocre sales, they have decided to focus only on their most popular product, ice cream with flavour of chocolate and vanilla.
In order to make a perfect such ice cream, it is important that the mixing machine receives equal amounts of vanilla and chocolate ice cream.
There are two separate creaming machines in the factory which produce respectively chocolate and vanilla ice cream, and the resulting creamy goodness is stored in two separate tanks. From there, it can be transported to the mixing machine through pipes, however the dimension of a pipe gives an upper bound for how much ice cream can pass through it each minute. These pipes meet in welding points, where streams of ice cream go from one pipe to another. Streams can also merge or split into other streams at such points, if more than two pipes meet here. It is not important to keep the flavors separate during the transportation, since they will eventually be mixed anyways.
Given a map of the pipe system, can you decide how many liters of ice cream the factory can produce each minute?
Input
The first line of input contains two integers $n$ ($3 \leq n \leq 200$) and $m$ ($2 \leq m \leq 1\, 000$), respectively the number of welding points, and the number of pipes. The second line contains three distinct integers $f$, $c$ and $v$ ($1 \leq f, c, v \leq n$), the welding points where respectively the mixing machine, the chocolate tank and the vanilla tank is connected to the pipe system.
Finally follows $m$ lines, the $i^{\text {th}}$ of which contains three non-negative integers $u_ i$, $v_ i$ and $x_ i$ ($1 \leq u_ i, v_ i \leq n$, $1 \leq x_ i \leq 1\, 000$). These indicate that there is a pipe between welding points $u_ i$ and $v_ i$ with a capacity for transporting $x_ i$ liters of ice cream per minute. Note that several pipes can go in parallel between the same welding points.
Output
A single integer, the maximum amount of ice cream the BGO factory can produce each minute (in liters).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 2 1 3 1 2 2 3 2 3 |
4 |
