Hack

时间限制：10s 空间限制：128MB

由于 FZYZ 教学区禁止使用手机，所以如何在一个课间通知到人就成了一个很大的问题。所幸，在不知道被信息传

递不及时坑了多少次之后，小叶子(@97littleleaf11)完美地解决了这个问题。小叶子组建了一张关系网，每一个

人是这张关系网上的一个节点(节点编号为[0,n-1])，两个人之间的通讯关系就是这张网上的一条有向边(一条 u->

v 的边意味着信息可以从u 传递到 v)。小叶子是 0 号节点，也是信息的发出者，n+e 是 n-1 号节点，在这个问

题中，他就是信息的接受者。一条信息从小叶子出发，可以沿着任意的边传递，最终传递给 n+e。在这个过程中，

一个人(包括小叶子和 n+e)可以经过多次，一条边也可以经过多次。经过多年的观察，小叶子发现这张关系网的每

一条边都是有可能被hack 的！当然每条边 hack 的代价是不一样的。所以，小叶子想要评价这个关系网的安全程

度。试想你要入侵这一张关系网，那么你只能事先选择一些边，将这些边hack 掉。如果一条边被 hack 了，就意

味着当信息从这条边传递的时候就会被截获。当然 n+e 也是非常厉害的！如果一条信息在传递过程中被截获两次

及以上，那么 n+e 就能用强大的智商定位出你的位置，那么这一次入侵就必然会失败。当然，如果 n+e 接收到了

消息，但是这条消息没有被截获，那么这次入侵也就是失败的。更精确地说，一次成功的入侵要满足以下条件：对

于任意一种可能的传递信息的方式(对应着一条从 0 到 n-1 的路径)，必须经过恰好一次被hack 的边。一次入侵

的代价就是你选择 hack 掉的边的代价和。小叶子想要知道，如果你拥有 n+e 这样超神的智商，而你又想最小化

代价，那么你入侵的代价会是多少呢？

第一行 n，m。表示点数及边数

接下来 m 行，每行三个整数 u,v,w，表示一条从 u 到 v 的代价为 w 的边。

2<=n<=100,m<=2500,1<=w<=10^9，0<=u,v<n,保证存在至少一条从0到n-1的路径。

输出一行，表示答案。,如果不存在合法的入侵方案，那么输出-1.

6
//hack 掉 0->1,2->4 这两条边

没有写明提示

没有写明来源