Migrated from Lutece 2988 时间的迷宫

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这个是一个有 $n$ 个时间点的故事，$1$ 为故事的起始点，$n$ 是故事的终结点。

时间穿越者晓美焰，在 $n$ 个时间点穿梭。

一次穿梭可以从一个时间点 $x_i$ 到另一个时间点 $y_i$（单向边），这条线被称为因果线。

晓美焰可以从起始点出发，通过这些因果线穿梭到终结点。

“无法避免的悲剧，无限的轮回，使晓美焰迷失在时间的迷宫中。”

成神之后，鹿目圆想斩断这个由因果线组成的迷宫，删去某些因果线，使得不存在任意一条路径能够从起始点到达终结点。

但是删除因果线是一件危险的事，需要满足一些条件，如果从起始点出发到终结点的同一条路径上发生两条因果线断裂，会给世界带来不可逆转的后果。

也就是说，任何一条从起始点通往终结点的路径上，只能删去一条因果线。（这个路径不一定是简单路径，只要是起点经过某种游走方式可以到达终点都算一条路径）

删去第 $i$ 条因果线需要耗费 $z_i$ 的神力，请计算鹿目圆最小需要多少耗费多少神力，在满足条件的情况下使得起始点无法到达终结点。

---

一句话题意： 任意一条路径只能删一条边，求最小割。

当然，如果一开始就没有从 $1$ 到 $n$ 的路径，那就不需要删除任何因果线，输出 $0$ 即可。

如果不存在任何满足条件的方案请输出 $-1$。

Input

第一行两个正整数 $n,m$，时间点数和因果线数。 下面 $m$ 行每行三个正整数 $x_i,y_i,z_i$，描述一条因果线连接的两个时间点，和删去它需要耗费的神力。

Output

存在满足条件的方案时输出一个数 $ans$，表示需要耗费的最小神力。 不存在方案时输出 $-1$ 即可。

Samples

6 7
1 2 5
1 3 5
2 4 1
3 5 1
5 2 1
4 6 5
5 6 5

6

4 4
1 2 5
2 3 2
3 4 2
4 2 2

5

Constraints

$2 ≤ n ≤ 1000, 1 ≤ m ≤ 2000$; $1 ≤ z_i ≤ 10^6,1\le x_i\ne y_i\le n$。

Note

在第二个样例中：我们认为1->2->3->4->2->3->4也是一条从起点到终点的路径，如果删去2->3的边，可以使得 $1$ 到 $n$ 不连通，但是2->3这条因果线在路径中出现了两次，所以这是不合法的方案。

数据保证无自环，重边视为不同的因果线。

Resources

2023 UESTC ICPC Training for Graph