#abc308h. [abc308_h]Make Q

[abc308_h]Make Q

现在有一个由 NN 个点组成的 MM 条边的简单无向图。一开始所有的边都是白色的。点编号为 1,2,3,,N1,2,3,\dots,N,第 ii 条边连接点 AiA_i, BiB_i,并且将这条边染为黑色的代价为 CiC_i。你现在需要染色至少四条边,使得:

1、除了某条染为黑色的边以外,剩下所有黑色的边构成一个简单环

2、不在该简单环上的黑色的边连接了一个该简单环上的点和一个不在任何环上的点。

请判断能否染色成功,如果能,输出最小代价,如果不能,则输出 -1