# your code goes here
from collections import defaultdict


def max_p(start):
    # print(root[1])
    return max(-x, d[start][0] + sum(map(max_p, d[start][1])))


for _ in range(int(input())):
    n, x = map(int, input().split())
    arr = list(map(int, input().split()))
    d = defaultdict(list)
    best_node = []
    for i in range(n):
        d[i + 1] = [arr[i], [], 0]

    for i in range(n - 1):
        a, b = map(int, input().split())
        d[a][1].append(b)

    p = max_p(1)
    # print(d)
    print(p)

'''
Test 1
2
12 5
5 2 10 5 6 3 -10 20 4 10 -15 -20
1 2
1 3
3 4
3 5
2 6
6 7
6 8
6 9
9 10
9 11
9 12
5 -4
5 6 -6 9 8
1 2
2 3
3 4
3 5
'''