Khi hành lang cứu trợ đã được xác định, trung tâm cần chuyển từ hoạt động cơ động sang vận hành lâu dài và mở rộng hệ thống cứu trợ. Một mạng vận chuyển cố định được xây dựng để duy trì phân phối vật tư lâu dài, phục vụ đồng thời nhiều điểm phân phối.

Hệ thống mạng vận chuyển cố định gồm ~N~ điểm được đánh số từ ~1~ đến ~N~ và ~N-1~ đoạn đường hai chiều, mỗi đoạn nối trực tiếp ~2~ điểm. Giữa ~2~ điểm bất kỳ trong hệ thống luôn tồn tại đường đi và hệ thống được xem như một cây. Điểm ~1~ là trung tâm điều hành. Mỗi điểm ~i~ có chỉ số hiệu quả là ~A_i~ nếu được chọn làm điểm phân phối vật tư. Chỉ số này có thể âm do điều kiện mặt bằng, nhân lực hoặc chi phí vận hành tại điểm đó không thuận lợi. Mỗi đoạn đường nối trực tiếp từ điểm ~u~ đến điểm ~v~ có một chi phí kích hoạt ~c~. Để phục vụ một điểm phân phối ~v~, tất cả các đoạn trên đường đi từ điểm ~1~ đến điểm ~v~ phải được kích hoạt. Một đoạn chỉ phải trả chi phí kích hoạt một lần, kể cả khi đoạn đó đồng thời phục vụ nhiều điểm phân phối.

Trung tâm cần xây dựng phương án chọn đúng ~K~ điểm làm điểm phân phối vật tư. Giá trị của một phương án bằng tổng chỉ số hiệu quả của ~K~ điểm được chọn trừ đi tổng chi phí của tất cả các đoạn phải kích hoạt.

Yêu cầu: Hãy giúp trung tâm tìm một phương án có giá trị lớn nhất.

Input

• Dòng ~1~ chứa hai số nguyên ~N, K~ ~(1 \le N \le 5 \cdot 10^4; 1 \le K \le \min(N, 50))~.

• Dòng ~2~ chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(-10^9 \le A_i \le 10^9)~.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, c~, biểu diễn đoạn đường hai chiều nối trực tiếp từ điểm ~u~ đến điểm ~v~ có chi phí kích hoạt ~c~ ~(1 \le u, v \le N; 1 \le c \le 10^9)~.

Output

Một dòng chứa một số nguyên duy nhất là giá trị lớn nhất của phương án tìm được.

Scoring

Sample Input 1

8 3
-6 5 14 6 16 2 13 11
1 2 2
2 3 13
1 4 5
3 5 17
5 6 11
5 7 5
4 8 14

Sample Output 1

6

Notes

Chọn các điểm ~3, 5~ và ~7~. Tổng chỉ số hiệu quả bằng ~14+16+13=43~. Các tuyến phải kích hoạt là: ~1-2, 2-3, 3-5~ và ~5-7~ với tổng chi phí ~2+13+17+5=37~. Giá trị phương án là ~43-37=6~.