Problem
Hari ini, Istana Aisne menganjurkan pesta pai yang disertai n kedai roti, setiap satunya mempunyai nombor uniknya dari 1 hingga n.
Sesetengah kedai roti disambungkan dengan jalan dua hala, tetapi dengan cara yang jika boleh berjalan kaki dari kedai roti i ke kedai roti j, maka terdapat betul-betul satu laluan di antara mereka.
Apabila En makan pai di kedai roti i-th, dia mendapat A
i keseronokan. Dan jika ia melalui jalan antara beberapa kedai roti dengan nombor v dan u, maka aroma pai yang lazat membawa keseronokan C
v,u.
En tidak mahu pergi ke setiap kedai roti lebih daripada sekali (sesetengahnya mungkin tidak pergi sama sekali), tetapi dia mahu memanfaatkan perayaan itu sepenuhnya.
Dia akan bermula di salah sebuah kedai roti dan hanya akan menyeberang antara mereka menggunakan jalan yang sedia ada.
Bantu En menentukan keseronokan maksimum yang boleh dia perolehi.
Input:
Baris pertama mengandungi nombor n (1 <= n <= 50000) - bilangan kedai roti dan nombor k - bilangan jalan sedia ada antara kedai roti.
Baris kedua mengandungi n nombor A
i (0 <= A
i <= 10000) - keseronokan pai di kedai roti ke-i.
Kemudian k baris mengikuti, setiap satu mengandungi 3 nombor v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), bermakna terdapat jalan di antara kedai roti bernombor v dan u, dan aroma di jalan ini membawa keseronokan C.
Output:
Cetak satu nombor - kepuasan maksimum yang mungkin.
Contoh:
| Input |
Output |
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 |
Penjelasan:
Dalam contoh pertama, anda perlu bermula di kedai roti pertama (1 hidangan), berjalan di sepanjang jalan antara kedai roti pertama dan kedua (1 hidangan), dan melawat kedai roti ke-2 (1 hidangan). Keseluruhan keseronokan - 1+1+1 = 3.
Dalam contoh kedua, anda perlu bermula di kedai roti ke-5 (10 keseronokan), berjalan di sepanjang jalan antara kedai roti ke-5 dan ke-4 (1 keseronokan), melawat kedai roti ke-4 (6 keseronokan), ikut jalan antara ke-4 dan ke-2 kedai roti (1 hidangan), melawat kedai roti ke-2 (5 hidangan), berjalan di sepanjang jalan antara kedai roti ke-2 dan ke-3 (10 hidangan), melawat kedai roti ke-3 (4 hidangan). Jumlah keseronokan - 10+1+6+1+5+10+4 = 37.