题目描述
给定一个 n 个点 m 条边的带权有向图,不存在自环,可能存在重边。求出一个权值和最小的边集的子集,使得存在至少一个点可以通过这些边到达所有点。
输入格式
第一行两个整数 n,m。
接下来 m 行一行三个整数 u,v,w,表示一条从 u 到 v 权值为 w 的有向边。
输出格式
输出一行一个整数表示满足要求的集合的最小权值和;若不存在,输出 −1。
样例
5 9
2 5 12
3 2 9
2 5 10
5 4 4
5 3 7
4 3 8
3 4 8
2 3 4
4 1 3
21
数据范围与提示
对于全部数据,1≤n≤500,1≤m≤2n(n−1),ui=vi,1≤wi≤109。
- 子任务 1(points:20):n≤10
- 子任务 2(points:20):n≤50
- 子任务 3(points:30):n≤100
- 子任务 4(points:30):n≤500