Problem
Hoje, o Castelo de Aisne está sediando um festival de tortas no qual participam n padarias, cada uma com seu próprio número exclusivo de 1 a n.
Algumas padarias são conectadas por estradas de mão dupla, mas de tal forma que se for possível caminhar da padaria i até a padaria j, então existe exatamente um caminho entre elas.
Quando En come tortas na i-ésima padaria, ele obtém prazeres A
i. E se passar na estrada entre algumas padarias com os números v e u, então o delicioso aroma de tortas traz prazer C
v,u.
En não quer ir a todas as padarias mais de uma vez (algumas podem nem ir), mas ela quer aproveitar ao máximo o festival.
Ele começará em uma das padarias e só cruzará entre elas usando as estradas existentes.
Ajude En a determinar o máximo prazer possível que ele pode obter.
Entrada:
A primeira linha contém o número n (1 <= n <= 50000) - o número de padarias, e o número k - o número de estradas existentes entre as padarias.
A segunda linha contém n números A
i (0 <= A
i <= 10000) - o prazer das tortas na i-ésima padaria.
Em seguida, seguem k linhas, cada uma contendo 3 números v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), o que significa que existe uma estrada entre padarias numeradas v e u, e o aroma desta estrada traz prazer C.
Saída:
Imprima um número - a máxima satisfação possível.
Exemplos:
| Entrada |
Saída |
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 |
Explicações:
No primeiro exemplo, você precisa começar na 1ª padaria (1 guloseima), caminhar ao longo da estrada entre a 1ª e a 2ª padaria (1 guloseima) e visitar a 2ª padaria (1 guloseima). Prazer total - 1+1+1 = 3.
No segundo exemplo, você precisa começar na 5ª padaria (10 prazeres), percorrer a estrada entre a 5ª e a 4ª padaria (1 prazer), visitar a 4ª padaria (6 prazeres), seguir a estrada entre a 4ª e a 2ª padaria (1 guloseima), visite a 2ª padaria (5 guloseimas), caminhe ao longo da estrada entre a 2ª e a 3ª padaria (10 guloseimas), visite a 3ª padaria (4 guloseimas). Prazer total - 10+1+6+1+5+10+4 = 37.