Y&Y

时间限制:10s      空间限制:128MB

题目描述

对于一本小说来说,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





提示


T<= 10 100% N<=250000


题目来源

没有写明来源

Menuappsclose