{"problem":{"name":"[CCPC 2023 北京市赛] 最小环","description":{"content":"小 I 发明了 $O(n + m)$ 的有向图最小环，于是他想考考你。 给定一个 $n$ 个节点、$m$ 条边的有向图，每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值，或者报告不存在环。 当然，由于你不会 $O(n + m)$ 的有向图最小环，于是小 I 放宽了条件：保证输入的图是弱连通的，且 $m-n$ 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10044"},"statements":[{"statement_type":"Markdown","content":"小 I 发明了 $O(n + m)$ 的有向图最小环，于是他想考考你。\n\n给定一个 $n$ 个节点、$m$ 条边的有向图，每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值，或者报告不存在环。\n\n当然，由于你不会 $O(n + m)$ 的有向图最小环，于是小 I 放宽了条件：保证输入的图是弱连通的，且 $m-n$ 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后图连通。\n\n## Input\n\n第一行两个整数 $n,m (1 \\le n \\le 3 \\times 10^5, -1 \\le m-n \\le 1500)$，表示图的点数和边数。\n\n接下来 $m$ 行每行三个整数 $u_i,v_i,w_i (1 \\le u_i,v_i \\le n, 1 \\le w_i \\le 10^9)$，表示一条从 $u_i$ 到 $v_i$、边权为 $w_i$ 的有向边。保证图是弱连通的。\n\n## Output\n\n如果图中不存在环，输出 `-1`，否则输出一个整数表示最小环的长度和。\n\n[samples]\n\n## Note\n\n**【样例解释 1】**\n\n最小环为 $1 \\to 2 \\to 4 \\to 3 \\to 1$。\n\n**【样例解释 3】**\n\n最小环为 $1 \\to 1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10044","tags":["2023","省赛/邀请赛"],"sample_group":[["4 6\n1 2 1\n4 3 3\n4 1 9\n2 4 1\n3 1 2\n3 2 6","7"],["1 0","-1"],["1 1\n1 1 1","1"]],"created_at":"2026-03-03 11:09:25"}}