题目内容

塔子哥有一题$n$个节点的树，树中每一条边都有一个权值，多多还有一个长度为$n$的正整数序列:$v_1,v_2,...,v_n$

删除树中若干条边之后(或者不删)，就会变成一个有$x$个连通块的图，此时的得分为：剩余边权和$+v_i$（两个可以互相到达的节点属于同一个连通块，注意一个孤点也是一个连通块）

塔子哥可以删除图中若干条边（可以不删）。现在塔子哥想知道，最多能够得到多少分。现在请你告诉塔子哥答案。

输入描述

第一行一个整数$T$，接下来有$T$组数据

每组数据第一行一个整数$n(2≤n≤10^5)$

第二行$n$个整数$v_1,...v_n(1≤v_i≤10^9)$

接下来$n-1$行，每行$3$个数，$a,b,w(1≤a,b≤n,1≤w≤10^4)$。

表示节点$a$与节点$b$之间有一条权值为w的边

保证$\sum \limits n$ 不超过$10^5$

保证每组数据给定的都是一棵树

输出描述

对于每组数据输出一行一个整数，表示最多能够得到多少分

示例1

输入

1
3
1 3 4
1 2 1
2 3 2

输出

5

说明

删除1与2之间的边，此时剩余边权和=2，连通块数量=2，得分=2+v[2]=2+3=5

示例2

输入

2
3
3 3 4
1 2 1
2 3 2
3
1 2 5
1 2 1
2 3 2

输出

6
5

说明

第一组数据：不删除任何边

第二组数据：删除所有边

示例3

输入

1
5
2 5 2 1 4
2 1 1
2 4 4
4 3 3
1 5 4

输出

16

说明

删除2到1之间的边，形成2个连通块，此时得分为16