Annettuna on n kaupunkia, jotka ovat kaikki yhteydessä toisiinsa n-1 tien välityksellä (eli kaupungit ja tiet muodostavat verkon, joka on puu). Jokaisessa kaupungissa on joko auringonkukkapelto tai satama.

Sato on valmiina korjattavaksi, ja tehtäväsi on löytää jokaiselta pellolta lyhin reitti satamaan. Mikä on näiden reittien kokonaispituus?

Syöte

Ensimmäisellä rivillä on kokonaisluku n: kaupunkien määrä. Kaupungit on numeroitu 1,2,\dots,n.

Toisella rivillä on n lukua t_1, t_2, \dots, t_n. Jos luku t_i on 0, kaupungissa i on satama, ja jos luku on 1, kaupungissa i on pelto. On varmaa, että vähintään yhdessä kaupungissa on satama.

Tämän jälkeen on n-1 riviä, joista jokaisella on kolme lukua a, b ja c: kaupunkien a ja b välillä on tie, jonka pituus on c.

Tuloste

Tulosta yksi kokonaisluku: lyhimpien reittien kokonaispituus.

Esimerkki

Syöte:

6
1 1 0 0 1 1
1 2 20
2 3 30
2 5 50
3 6 60
1 4 10

Tuloste:

180

Selitys: Seuraava kuva vastaa esimerkkisyötettä:

Osatehtävä 1 (33 pistettä)

• 1 \le n \le 1000
• 1 \le c \le 1000

Osatehtävä 2 (67 pistettä)

• 1 \le n \le 2\cdot10^5
• 1 \le c \le 1000