• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• Dad, I don’t have any T-shirts!
• Don’t worry son! I’m going to take a contest soon. I will bring you one.

Reza loves to participate in contests all over the country. He registers into contests for the living and not only makes his wife happy with the prize but also brings the T-shirts to his son. Obviously, Reza only participates in the contests which their transportation costs are not higher than their prize. In such cases, he will travel from Tehran to the city, takes the contest and travels back to Tehran to reward the prize and the T-shirt to his wife and son immediately. Reza’s wife wants to go shopping for the New Year soon, but she is not sure if Reza can afford the money. Help her to calculate the total money that Reza is able to earn from the contests. (Reza is an expert in ACM contests and he will win the prize in any contest he participates in)

ورودی

In the first line there will be an integer $T$ indicating the number of test cases. $$1 \leq T \leq 100$$

Each test case begins with two integer $N$ and $M$ the number of cities hosting the contests and the number of roads between them respectively. $$1 \leq N \leq 10^3$$ $$1 \leq M \leq \frac{N(N - 1)}{2}$$

In the following $N$ lines, comes an integer $P_i$ indicating the prize of city $i$. $$1 \leq P_i \leq 10^9$$

The next following $M$ lines contain three integers $u, v$ and $w$ which means the cities $u$ and $v$ are connected to each other and the transportation cost between them is $w$.

$$1 \leq w \leq 100$$

Assume that Reza begins from Tehran (city $0$) and comes back to Tehran after each contest.

خروجی

For each test case print the maximum money that Reza can earn from participating in the contest in a line

مثال‌ها

ورودی نمونه ۱

2

3 4
7 10 25
0 3 11
0 2 5
1 3 8
1 2 16

3 3
10 20 30
0 1 4
1 2 6
2 3 10

خروجی نمونه ۱

35
30