Flow

Pang의 연구 관심사 중 하나는 최대 유량 문제이다.

정점이 $n$개인 방향 그래프 $G$가 다음 조건을 만족하면 universe라고 한다.

• $G$는 정점 $1$에서 정점 $n$으로 가는, 길이가 같은 $k$개의 정점 독립인 단순 경로의 합집합이다.

경로 집합이 정점 독립이라는 것은 내부 정점을 공유하지 않는다는 뜻이다.

경로에서 내부 정점이란 그 경로의 끝점이 아닌 정점을 말한다.

경로가 단순하다는 것은 정점이 모두 서로 다르다는 뜻이다.

정점이 $n$개, 간선이 $m$개인 universe 그래프 $G$가 주어진다. 각 간선에는 음이 아닌 정수 용량이 있다. 정점 $1$에서 정점 $n$으로 가는 최대 유량을 최대한 크게 만들기 위해 다음 연산을 원하는 만큼(0번 포함) 수행할 수 있다.\

양의 용량을 가진 간선 $e$를 하나 잡아 $e$의 용량을 $1$ 줄이고 다른 간선 하나의 용량을 $1$ 늘린다.\

Pang은 이를 달성하기 위한 최소 연산 횟수를 알고 싶어 한다.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($2\leq n\leq 100000, 1\leq m \leq 200000$).

다음 $m$개 줄에 각각 세 정수 $x, y, z$가 주어지며, 이는 $x$에서 $y$로 가는 용량 $z$인 간선을 나타낸다 ($1 \leq x, y \leq n$, $0\le z\le 1000000000$).

입력은 중복 간선과 자기 자신으로 가는 간선이 없는 $universe$ 그래프임이 보장된다.

최소 연산 횟수를 한 줄에 출력한다.