题目描述

对于一本小说来说，Y&Y 元素是很重要的。对于某一个深谙此道的人来说，Y&Y 更是一种符号，一种象征。

在研究一棵树的时候，他惊喜的发现了这种象征。于是他希望在这棵树中找到最大的两个 $Y$。

在树中的一个 $Y$ 定义为一个中心点，以及与之相连的 $3$ 条非空的链，且这三条链除了中心点之外没有其他的公共点。也就是说，一个 $Y$ 最少有 $4$ 个点。当然每一条链可以不断延长。一个 $Y$ 的权值定义为这个 $Y$ 包含的所有边的边权之和。

你的任务是对于输入的树，在其中找到两个不相交（既没有公共点，也没有公共边）$Y$，使两个 $Y$ 的权值之和最大。

输入格式

本题含有多组数据。

文件的第一行有一个正整数 $t$，表示数据组数。

接下来一共会有 $t$ 个输入块。

对于每一个数据块：

第一行有两个正整数 $n,m$，表示这棵树的节点数和边数。

接下来的 $m$ 行，每行 $3$ 个数 $i,j,k$，分别表示一条边的两个节点编号 $(i,j)$ 以及边的权值 $k$。

输出格式

对于每一组数据，输出一行：

最大的 Y&Y 权值之和，或者，如果不能找到两个不相交的 $y$，输出 POOR BB。

1
9 8
1 2 6
2 3 5
2 4 5
4 5 3
4 6 4
6 7 3
7 8 9
7 9 7

38

数据规模与约定

对于 $100\%$ 的数据，$t<= 10$，$n<=250000$。