3115. [BZOJ 4663] Hack

【题目描述】

一张 n 个点 m 条边的有向图，点从 0 到 n-1 编号，每条边有权值 t[i]。你需要选择一些边，使得任意从 0 到 n-1 的路径都经过了恰好一次你选择的边，并最小化选择的边的权值和。

【输入格式】

第一行两个整数 n,m，表示点数和边数。

接下来 m 行，每行三个整数 u[i],v[i],t[i]，描述一条从 u[i]到 v[i]，权值为 t[i]的有向边。

【输出格式】

如果不存在方案，则输出-1；否则输出最小的权值和。

【样例输入】

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

【样例输出】

6

【提示】

对于 30%的数据，m≤15

对于 50%的数据，n≤15

对于 100%的数据，2≤n≤100,m≤2500,1≤t[i]≤10^9

保证存在至少一条从 0 到 n-1 的路径。