Submit | All submissions | Best solutions | Back to list |

## 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 2Output: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 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD 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 |