# 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
'''
IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmZyb20gY29sbGVjdGlvbnMgaW1wb3J0IGRlZmF1bHRkaWN0CgoKZGVmIG1heF9wKHN0YXJ0KToKICAgICMgcHJpbnQocm9vdFsxXSkKICAgIHJldHVybiBtYXgoLXgsIGRbc3RhcnRdWzBdICsgc3VtKG1hcChtYXhfcCwgZFtzdGFydF1bMV0pKSkKCgpmb3IgXyBpbiByYW5nZShpbnQoaW5wdXQoKSkpOgogICAgbiwgeCA9IG1hcChpbnQsIGlucHV0KCkuc3BsaXQoKSkKICAgIGFyciA9IGxpc3QobWFwKGludCwgaW5wdXQoKS5zcGxpdCgpKSkKICAgIGQgPSBkZWZhdWx0ZGljdChsaXN0KQogICAgYmVzdF9ub2RlID0gW10KICAgIGZvciBpIGluIHJhbmdlKG4pOgogICAgICAgIGRbaSArIDFdID0gW2FycltpXSwgW10sIDBdCgogICAgZm9yIGkgaW4gcmFuZ2UobiAtIDEpOgogICAgICAgIGEsIGIgPSBtYXAoaW50LCBpbnB1dCgpLnNwbGl0KCkpCiAgICAgICAgZFthXVsxXS5hcHBlbmQoYikKCiAgICBwID0gbWF4X3AoMSkKICAgICMgcHJpbnQoZCkKICAgIHByaW50KHApCgonJycKVGVzdCAxCjIKMTIgNQo1IDIgMTAgNSA2IDMgLTEwIDIwIDQgMTAgLTE1IC0yMAoxIDIKMSAzCjMgNAozIDUKMiA2CjYgNwo2IDgKNiA5CjkgMTAKOSAxMQo5IDEyCjUgLTQKNSA2IC02IDkgOAoxIDIKMiAzCjMgNAozIDUKJycn