Сегодня в замке Эна проходит фестиваль пирогов, в котором участвуют n пекарен, каждая из которых имеет свой уникальный номер от 1 до n.
Некоторые пекарни соединены между собой двусторонними дорогами, но таким образом, что если из пекарни i можно дойти до пекарни j, то существует ровно один маршрут между ними.
Когда Эн ест пироги в i-й пекарне, то он получает A
i удовольствия. А если проходит по дороге между некоторыми пекарнями с номерами v и u, то вкусный аромат пирогов приносит Эну C
v,u удовольствия.
Эн не хочет появляться в каждой пекарне больше одного раза (в некоторые можно не заходить вообще), но при этом хочет получить от фестиваля максимально возможное удовольствие.
Он начнет в какой-либо из пекарен и далее будет переходить между ними только по существующим дорогам.
Помогите Эну определить максимально возможное удовольствие, которое он сможет получить.
Входные данные:
В первой строке дано число n (1 <= n <= 50000) - количество пекарен, и число k - количество существующих дорог между пекарнями.
Во второй строке дано n чисел A
i (0 <= A
i <= 10000) - удовольствие от пирогов i-й пекарне.
Далее следует k строк, в каждой по 3 числа v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), означающие, что существует дорога между пекарнями с номерами v и u, и аромат на этой дороге приносит C удовольствия.
Выходные данные:
Выведите одно число - максимально возможное удовльствие.
Примеры:
| Входные данные |
Выходные данные |
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 |
Пояснения:
В первом примере нужно начать в 1-й пекарне (1 удовольствие), пройти по дороге между 1-й и 2-й пекарнями (1 удовольствие) и посетить 2-ю пекарню (1 удовольствие). Суммарное удовольствие - 1+1+1 = 3.
Во втором примере нужно начать в 5-й пекарне (10 удовольствия), пройти по дороге между 5-й и 4-й пекарнями (1 удовольствие), посетить 4-ю пекарню (6 удовольствия), пройти по дороге между 4-й и 2-й пекарнями (1 удовольствие), посетить 2-ю пекарню (5 удовольствия), пройти по дороге между 2-й и 3-й пекарнями (10 удовольствия), посетить 3-ю пекарню (4 удовольствия). Суммарное удовольствие - 10+1+6+1+5+10+4 = 37.