Problem
Aujourd'hui, le Château de l'Aisne accueille une fête de la tarte à laquelle participent n boulangeries, chacune ayant son propre numéro unique de 1 à n.
Certaines boulangeries sont reliées par des routes à double sens, mais de telle sorte que s'il est possible de marcher de la boulangerie i à la boulangerie j, alors il y a exactement un itinéraire entre elles.
Quand En mange des tartes dans la ième boulangerie, il obtient les plaisirs d'A
i. Et s'il passe le long de la route entre des boulangeries portant les numéros v et u, alors le délicieux arôme des tartes apporte du plaisir à C
v,u.
En ne veut pas aller plus d'une fois dans toutes les boulangeries (certaines n'y vont peut-être pas du tout), mais elle veut tirer le meilleur parti du festival.
Il commencera à l'une des boulangeries et ne les traversera qu'en empruntant les routes existantes.
Aidez En à déterminer le maximum de plaisir possible qu'il peut obtenir.
Saisie :
La première ligne contient le nombre n (1 <= n <= 50000) - le nombre de boulangeries, et le nombre k - le nombre de routes existantes entre les boulangeries.
La deuxième ligne contient n nombres A
i (0 <= A
i <= 10000) - le plaisir des tartes dans la ième boulangerie.
Viennent ensuite k lignes contenant chacune 3 nombres v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), signifiant qu'il y a une route entre boulangeries numérotées v et u, et l'arôme sur cette route apporte du plaisir C.
Sortie :
Imprimez un numéro - la satisfaction maximale possible.
Exemples :
| Entrée |
Sortie |
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 |
Explications :
Dans le premier exemple, vous devez commencer à la 1ère boulangerie (1 friandise), marcher le long de la route entre les 1ère et 2ème boulangeries (1 friandise) et visiter la 2ème boulangerie (1 friandise). Plaisir total - 1+1+1 = 3.
Dans le deuxième exemple, il faut partir de la 5ème boulangerie (10 plaisirs), longer la route entre les 5ème et 4ème boulangeries (1 plaisir), visiter la 4ème boulangerie (6 plaisirs), suivre la route entre la 4ème et la 2ème boulangerie (1 friandise), visite 2e boulangerie (5 friandises), promenade le long de la route entre les 2e et 3e boulangeries (10 friandises), visite 3e boulangerie (4 friandises). Plaisir total - 10+1+6+1+5+10+4 = 37.