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

    ID: 1334 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论最小生成树雅礼集训2018

「雅礼集训 2018 Day8」A

题目描述

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

输入格式

第一行两个整数 n,mn, m

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

输出格式

输出一行一个整数表示满足要求的集合的最小权值和;若不存在,输出 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
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$。

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