Given a directed graph with $n$ vertices and $m$ edges, where vertices are numbered from $1$ to $n$, and each edge $(u, v)$ has a capacity $c$ associated with it, the objective is to determine the maximum flow from a given source vertex $S$ to a given destination vertex $T$.
### Input
- The first line contains four integers $n,m,S,T$.
- The next $m$ lines, each line contains three integers $u,v,c$, there is an edge of capacity $c$ from $u$ to $v$. There are no self loops or duplicate edges in the graph.
### Output
- Print the maximum flow.
### Constraints
- $1 \le n \le 500$.
- $1 \le m \le 5 \times 10^4$.
- $1 \le u,v \le n$.
- $1 \le c \le 10^4$.
### Example
Input:
```
6 8 1 6
5 6 6
4 6 6
3 5 1
3 4 3
2 5 3
2 4 6
1 3 5
1 2 5
```
Output:
```
9
```
