QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB
[+3]

# 7991. 最小环

Statistics

题目描述

小 I 发明了 O(n+m) 的有向图最小环,于是他想考考你。

给定一个 n 个节点、m 条边的有向图,每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值,或者报告不存在环。

当然,由于你不会 O(n+m) 的有向图最小环,于是小 I 放宽了条件:保证输入的图是弱连通的,且 mn 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后图连通。

输入格式

从标准输入读入数据。

第一行两个整数 n,m(1n3×105,1mn1500),表示图的点数和边数。

接下来 m 行每行三个整数 ui,vi,wi(1ui,vin,1wi109),表示一条从 uivi、边权为 wi 的有向边。保证图是弱连通的。

输出格式

输出到标准输出。

如果图中不存在环,输出 -1,否则输出一个整数表示最小环的长度和。

样例

输入

4 6
1 2 1
4 3 3
4 1 9
2 4 1
3 1 2
3 2 6

输出

7

解释

最小环为 12431

样例

输入

1 0

输出

-1

样例

输入

1 1
1 1 1

输出

1

解释

最小环为 11