Problem
Hoy, el Castillo de Aisne acoge un festival de pasteles en el que participan n panaderías, cada una de las cuales tiene su propio número único del 1 al n.
Algunas panaderías están conectadas por caminos de doble sentido, pero de tal manera que si es posible caminar de la panadería i a la panadería j, entonces hay exactamente una ruta entre ellas.
Cuando En come pasteles en la i-ésima panadería, obtiene placeres A
i. Y si pasa por el camino entre algunas panaderías con los números v y u, entonces el delicioso aroma de los pasteles trae placer a C
v,u.
En no quiere ir a todas las panaderías más de una vez (puede que algunas no vayan nunca), pero quiere aprovechar al máximo el festival.
Comenzará en una de las panaderías y solo cruzará entre ellas utilizando las carreteras existentes.
Ayuda a En a determinar el máximo placer posible que puede obtener.
Entrada:
La primera línea contiene el número n (1 <= n <= 50000) - el número de panaderías, y el número k - el número de caminos existentes entre las panaderías.
La segunda línea contiene n números A
i (0 <= A
i <= 10000) - el placer de los pasteles en la i-ésima panadería.
Luego siguen k líneas, cada una de las cuales contiene 3 números v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), lo que significa que hay un camino entre panaderías numeradas v y u, y el aroma en este camino trae C placer.
Salida:
Imprima un número: la máxima satisfacción posible.
Ejemplos:
| Entrada |
Salida |
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 |
Explicaciones:
En el primer ejemplo, debe comenzar en la primera panadería (1 premio), caminar por el camino entre la primera y la segunda panadería (1 premio) y visitar la segunda panadería (1 premio). Placer total - 1+1+1 = 3.
En el segundo ejemplo, debe comenzar en la panadería 5 (10 placeres), caminar por el camino entre las panaderías 5 y 4 (1 placer), visitar la panadería 4 (6 placeres), seguir el camino entre el 4 y 2 panadería (1 golosina), visita la 2.ª panadería (5 golosinas), camina por la carretera entre la 2.ª y la 3.ª panadería (10 golosinas), visita la 3.ª panadería (4 golosinas). Placer total - 10+1+6+1+5+10+4 = 37.