Thành phố A nổi tiếng với nhiều danh lam thắng cảnh, hiện thành phố có \(n\) điểm du lịch được đánh số từ \(1\) đến \(n\), các điểm được nối với nhau bởi \(n -1\) con đường \(2\) chiều, các điểm liên thông với nhau, nghĩa là luôn có đường đi giữa \(2\) thành điểm bất kì trong thành phố. Thành phố A hiện tại thành phố bắt đầu cho thuê các địa điểm du lịch này. Có \(m\) đoàn du lịch, đoàn thứ \(i\) muốn thuê các điểm du lịch trên đường đi ngắn nhất từ \(u_i\) đến \(v_i\) với giá là \(c_i\). Vì muốn nâng cao chất lượng kinh tế, chủ tịch thành phố quyết định cho các đoàn du lịch thuê các địa điểm, nhưng vì quá bận nên chủ tịch nhờ bạn chọn các đoàn du lịch sao cho lợi nhuận thu về là lớn nhất thỏa mãn điều kiện là ở \(1\) điểm bất kì chỉ được thuê bởi nhiều nhất \(1\) đoàn du lịch.

Input:

• Dòng thứ nhất chứa \(2\) số nguyên dương \(n\) và \(m\) (\(1 \le n, m \le 10^5\)).
• \(n - 1\) dòng tiếp theo lần lượt là \(2\) số \(u\) và \(v\) biểu thị có đường đi giữa \(u\) và \(v\) .
• \(m\) dòng tiếp theo là lần lượt là các số \(u_i, v_i, c_i\) (\(1 \le u_i, v_i \le n\), \(1 \le c_i \le 10 ^5\)).

Output:

• Gồm một số duy nhất là lợi nhuận lớn nhất có thể nhận được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(1 \le n, m \le 300\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 6
1 2
2 3
3 4
4 5
1 5 59535
2 3 9850
1 2 13264
1 4 46643
2 4 17545
4 5 97294

110558