Problem
Today, the Aisne Castle is hosting a pie festival in which n bakeries participate, each of which has its own unique number from 1 to n.
Some bakeries are connected by two-way roads, but in such a way that if it is possible to walk from bakery i to bakery j, then there is exactly one route between them.
When En eats pies in the i-th bakery, he gets A
i pleasures. And if it passes along the road between some bakeries with numbers v and u, then the delicious aroma of pies brings C
v,u pleasure.
En doesn't want to go to every bakery more than once (some may not go at all), but she wants to get the most out of the festival.
He will start at one of the bakeries and will only cross between them using the existing roads.
Help En determine the maximum possible pleasure he can get.
Input:
The first line contains the number n (1 <= n <= 50000) - the number of bakeries, and the number k - the number of existing roads between the bakeries.
The second line contains n numbers A
i (0 <= A
i <= 10000) - the pleasure of pies in the i-th bakery.
Then k lines follow, each containing 3 numbers v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), meaning that there is a road between bakeries numbered v and u, and the aroma on this road brings C pleasure.
Output:
Print one number - the maximum possible satisfaction.
Examples:
| Input |
Output |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
Explanations:
In the first example, you need to start at the 1st bakery (1 treat), walk along the road between the 1st and 2nd bakeries (1 treat), and visit the 2nd bakery (1 treat). Total pleasure - 1+1+1 = 3.
In the second example, you need to start at the 5th bakery (10 pleasures), walk along the road between the 5th and 4th bakeries (1 pleasure), visit the 4th bakery (6 pleasures), follow the road between the 4th and 2nd bakery (1 treat), visit 2nd bakery (5 treats), walk along the road between 2nd and 3rd bakeries (10 treats), visit 3rd bakery (4 treats). Total pleasure - 10+1+6+1+5+10+4 = 37.