D. Maximum profit (profit)

There are railway stations. A chain hotel wants to open restaurants at the railway station, but the government does not allow it to operate at two connected railway stations at the same time. Any two railway stations have one and only one route. Now that the profit of opening a restaurant at each railway station is known, find the maximum profit of this chain hotel.

The first line is a positive integer , indicating the number of data groups; in each group of data, the first line is a positive integer , which indicates the number of train stations, the number is from to , and the next lines , Each line has two positive integers , , respectively, indicating that there is a direct path between and railway stations, and the last line is positive integers , respectively Profit from operating a restaurant at a railway station.

Output the maximum profit.

输入样例

2
6
1 3
3 4
4 5
2 3
4 6
10 20 25 40 30 30
???

输出样例

90
?

题目描述
有 个火车站，某连锁饭店要在火车站开饭店，但政府不允许它同时开在两个相连接的火车站，任意两个火车站有且只有一条路径。现在已知在每个火车站开饭店的利润，求这个连锁饭店的最大利润。

输入格式
第一行为正整数 ，表示数据组数；
每组数据中，第一行为正整数 ，表示火车站个数，编号从1到 ，
接下来 行，每行两个正整数 ,()，分别表示 和 火车站之间有一条直达路径，最后一行是 个正整数 ()，分别表示在每个火车站开饭店的利润。

输出格式
输出最大利润。