23455번 - Flow 다국어

문제

One of Pang's research interests is the maximum flow problem.

A directed graph $G$ with $n$ vertices is universe if the following condition is satisfied:

• $G$ is the union of $k$ vertex-independent simple paths from vertex 1ドル$ to vertex $n$ of the same length.

A set of paths is vertex-independent if they do not have any internal vertex in common.

A vertex in a path is called internal if it is not an endpoint of that path.

A path is simple if its vertices are distinct.

Let $G$ be a universe graph with $n$ vertices and $m$ edges. Each edge has a non-negative integral capacity. You are allowed to perform the following operation any (including 0ドル$) times to make the maximum flow from vertex 1ドル$ to vertex $n$ as large as possible:\\

Let $e$ be an edge with positive capacity. Reduce the capacity of $e$ by 1ドル$ and increase the capacity of another edge by 1ドル$.\\

Pang wants to know what is the minimum number of operations to achieve it?

입력

The first line contains two integers $n$ and $m$ (2ドル\leq n\leq 100000, 1\leq m \leq 200000$).

Each of the next $m$ lines contains three integers $x, y$ and $z,ドル denoting an edge from $x$ to $y$ with capacity $z$ (1ドル \leq x, y \leq n,ドル 0ドル\le z\le 1000000000$).

It's guaranteed that the input is a $universe$ graph without multiple edges and self-loops.

출력

Output a single integer --- the minimum number of operations.

제한

힌트