Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

FLOW - Maximum Flow

Given a graph with n (2 ≤ n ≤ 50) vertices numbered 1 to n and m (1 ≤ m ≤ 1000) directed, weighted edges, compute the maximum flow  from vertex 1 to vertex n.

Input

The first line contains the two integers n and m. The next m lines each contain three integers u, v, and c, denoting that there is an edge (u,v) of capacity c, where 1 ≤ c ≤ 1000 and 1 ≤ u, v ≤ n.

Output

Output the value of the maximum flow from 1 to n.

Example

Input:
4 5
1 2 3
1 3 4
2 4 4
3 2 1
3 4 2
Output: 6

Added by:Thomas Thierauf
Date:2012-04-12
Time limit:0.208s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.