Problem
Hôm nay, Lâu đài Aisne đang tổ chức một lễ hội bánh có n tiệm bánh tham gia, mỗi tiệm có một số duy nhất từ 1 đến n.
Một số tiệm bánh được nối với nhau bằng đường hai chiều, nhưng theo cách sao cho nếu có thể đi bộ từ tiệm bánh i đến tiệm bánh j thì có đúng một con đường giữa chúng.
Khi Én ăn bánh ở tiệm bánh thứ i, nó
i thích thú. Và nếu nó đi dọc con đường giữa một số tiệm bánh có số v và u, thì hương vị thơm ngon của những chiếc bánh nướng sẽ mang lại cho C
v,u niềm vui.
En không muốn đi đến mọi tiệm bánh nhiều hơn một lần (một số có thể không đi lần nào), nhưng cô ấy muốn tận dụng tối đa lễ hội.
Anh ta sẽ bắt đầu tại một trong các tiệm bánh và sẽ chỉ băng qua chúng bằng những con đường hiện có.
Hãy giúp En xác định khoái cảm tối đa mà En có thể đạt được.
Đầu vào:
Dòng đầu tiên chứa số n (1 <= n <= 50000) - số lượng cửa hàng bánh mì và số k - số lượng đường hiện có giữa các cửa hàng bánh mì.
Dòng thứ hai chứa n số A
i (0 <= A
i <= 10000) - niềm vui của những chiếc bánh trong tiệm bánh thứ i.
Sau đó k dòng tiếp theo, mỗi dòng chứa 3 số v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), nghĩa là có một đường nằm giữa tiệm bánh đánh số v và u, mùi thơm trên con đường này làm C thích thú.
Đầu ra:
In một số - sự hài lòng tối đa có thể.
Ví dụ:
| Đầu vào |
Đầu ra |
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 |
Giải thích:
Trong ví dụ đầu tiên, bạn cần bắt đầu tại tiệm bánh thứ nhất (1 món), đi bộ dọc theo con đường giữa tiệm bánh thứ 1 và thứ 2 (1 món) và ghé thăm tiệm bánh thứ 2 (1 món). Tổng số niềm vui - 1+1+1 = 3.
Trong ví dụ thứ hai, bạn cần bắt đầu từ tiệm bánh thứ 5 (10 thú vui), đi bộ dọc theo con đường giữa tiệm bánh thứ 5 và thứ 4 (1 thú vui), ghé thăm tiệm bánh thứ 4 (6 thú vui), đi theo con đường giữa tiệm bánh thứ 4 và thứ 2 tiệm bánh (1 món), ghé tiệm bánh thứ 2 (5 món), đi dọc con đường giữa tiệm bánh thứ 2 và thứ 3 (10 món), ghé tiệm bánh thứ 3 (4 món). Tổng khoái cảm - 10+1+6+1+5+10+4 = 37.