P14489 [集训队互测 2018] 小修和小栋生成树

试题来源：，向 LOJ 和出题人表示感谢。如果版权方并不希望试题出现在洛谷，可联系洛谷管理组撤下试题。

这**不是**一道提交答案题。 这**不是**一道交互题。 小修正在和小栋一起造生成树。 他们各有一张 $n$ 个点，$m$ 条边的图。他们希望在图中找出一些边，使得只含有这些边的图是森林或者环套树森林。 由于小修和小栋是情侣，所以他们决定作出一样的选择，具体来说，对于第 $i$ 条边，两个人要么同时选择，要么同时不选择。 对于第 $i$ 条边有 $a_i$ 的权值，小修和小栋希望最终选择出来的边的权值和尽量大。 这里环套树森林的定义指的是每个联通块都是树或者环套树。

第一行包含两个整数 $n$ 和 $m$，表示图的点数和边数。 接下来一行两个整数 $\text{type}_1,\text{type}_2$，分别表示小修对最终图的要求和小栋的要求，当 $\text{type}$ 为 $1$ 的时候，表示希望最后得到的是森林，如果 $\text{type}$ 为 $2$ 则是环套树森林。 接下来 $m$ 行，每行 $5$ 个整数 $u1_i,v1_i,u2_i,v2_i,a_i$，其中 $u1_i,v1_i$ 表示这条边在小修的图中连接的点，$u2_i,v2_i$ 表示在小栋的图中连接的点。 数据不保证没有重边和自环。

输出一行一个整数，表示最大的边权和。

对于所有数据，满足 $1\le n,m\le 300,1\le a_i\le 10^5$ 以下限制如不做特殊说明均表示不超过。 |子任务编号|$n$|$m$|特殊限制|分数| |:----:|:--:|:----:|:--:|:----:| |$1$| $300$| $300$| $u1_i=u2_i,v1_i=v2_i$ | $3$| |$2$| $300$| $20$ |无| $3$| |$3$| $7$| $300$ |$\text{type}_1=\text{type}_2=1$ | $7$| |$4$| $5$| $300$| 无| $11$| |$5$| $300$| $300$ |$\text{type}_1=\text{type}_2=1$| $15$| |$6$| $300$| $300$ |$\text{type}_1=\text{type}_2=2$| $17$| |$7$| $70$| $70$| 无 |$10$| |$8$| $300$ |$300$| 无 |$34$|