题目描述

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

输入格式

第一行两个整数 $n, m$。

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

输出格式

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

样例

input

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

output

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$