#6510. 「雅礼集训 2018 Day8」A

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个 n 个点 m 条边的带权有向图,不存在自环,可能存在重边。求出一个权值和最小的边集的子集,使得存在至少一个点可以通过这些边到达所有点。

输入格式

第一行两个整数 n, m

接下来 m 行一行三个整数 u, v, w ,表示一条从 u v 权值为 w 的有向边。

输出格式

输出一行一个整数表示满足要求的集合的最小权值和;若不存在,输出 -1

样例

样例输入 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

样例输出 1

21

数据范围与提示

对于全部数据, 1 \leq n \leq 500, 1 \leq m \leq \frac{n(n-1)}{2}, u_i \neq v_i, 1 \leq w_i \leq 10^9

  • 子任务 \rm 1(points: 20) n \leq 10
  • 子任务 \rm 2(points: 20) n \leq 50
  • 子任务 \rm 3(points: 30) n \leq 100
  • 子任务 \rm 4(points: 30) n \leq 500