Problem
Oggi, il castello di Aisne ospita una festa della torta a cui partecipano n pasticcerie, ognuna delle quali ha il proprio numero univoco da 1 a n.
Alcune panetterie sono collegate da strade a doppio senso, ma in modo tale che se è possibile camminare dalla panetteria i alla panetteria j, allora c'è esattamente un percorso tra di loro.
Quando En mangia torte nell'i-esimo panificio, ottiene piaceri A
i. E se passa lungo la strada tra alcune panetterie con i numeri v e u, allora il delizioso aroma delle torte porta C
v,u piacere.
En non vuole andare in tutte le pasticcerie più di una volta (alcuni potrebbero non andarci affatto), ma vuole ottenere il massimo dal festival.
Inizierà da una delle panetterie e le attraverserà solo utilizzando le strade esistenti.
Aiuta En a determinare il massimo piacere possibile che può ottenere.
Inserimento:
La prima riga contiene il numero n (1 <= n <= 50000) - il numero di panetterie e il numero k - il numero di strade esistenti tra le panetterie.
La seconda riga contiene n numeri A
i (0 <= A
i <= 10000) - il piacere delle torte nell'i-esimo panificio.
Quindi seguono k linee, ciascuna contenente 3 numeri v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), a significare che c'è una strada tra panetterie numerate v e u, e l'aroma su questa strada porta piacere C.
Uscita:
Stampa un numero: la massima soddisfazione possibile.
Esempi:
| Input |
Uscita |
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 |
Spiegazioni:
Nel primo esempio, devi iniziare dal 1° panificio (1 dolcetto), camminare lungo la strada tra il 1° e il 2° panettiere (1 dolcetto) e visitare il 2° panificio (1 dolcetto). Piacere totale - 1+1+1 = 3.
Nel secondo esempio, devi iniziare dal 5° panificio (10 piaceri), camminare lungo la strada tra il 5° e il 4° panificio (1 piacere), visitare il 4° panificio (6 piaceri), seguire la strada tra il 4° e il 2° panificio (1 dolcetto), visita 2° panificio (5 dolcetti), passeggiata lungo la strada tra il 2° e il 3° panettiere (10 dolcetti), visita 3° panificio (4 dolcetti). Piacere totale - 10+1+6+1+5+10+4 = 37.