최대 유량 (기본)

방향 용량 그래프에서 소스 S에서 싱크 T까지의 최대 유량을 구한다.

각 간선에는 용량(capacity)이 있으며, 유량은 용량을 초과할 수 없다. 같은 두 정점 사이에 간선이 여럿 있을 수 있다.

입력

첫째 줄에 정점 수 N과 간선 수 M이 주어진다.

다음 M개 줄에 간선의 출발 정점 u, 도착 정점 v, 용량 c가 주어진다.

마지막 줄에 소스 S와 싱크 T가 주어진다.

• 2 ≤ N ≤ 50
• 1 ≤ M ≤ 1,000
• 1 ≤ c ≤ 1,000

출력

최대 유량을 출력한다.

예제 입력 1

6 9
1 2 12
1 3 13
2 4 10
3 2 4
3 5 14
4 6 7
5 4 7
5 6 4
4 3 1
1 6

예제 출력 1

23