题目描述
给出有向图 $G$，请你割掉一些边，使得 $1$ 不能到 $n$，并且割掉的边权值和最大。
输入格式
第一行两个正整数 $n,m$，为点数和边数。
接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x\to y$ 的边权值为 $z$。$(1\le x,y\le n)$
输出格式
一行一个正整数，为最大割大小。
样例
输入
2 3
1 2 2
1 2 3
1 1 0输出
5解释
前两条边都割。
数据范围
第 $1,2$ 组数据：$n,m\le 10$。
第 $3,4$ 组数据：$z>0$。
第 $1\sim 10$ 组数据：$2\le n\le 500$，$1\le m\le 10000$，$|z|\le 10^{15}$。