Lưu ý: hiện tại bài đang lỗi không thể chấm bằng file .inp .out, nên các bạn không cần freopen mà chỉ cần nhập bằng màn hình và in ra màn hình thôi nhé

Khu đô thị mới VINNEXT gồm \(N\) biệt thự được đánh số thứ tự từ 1 đến \(N\), các biệt thự được kết nối với nhau bởi đúng \(N-1\) đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp giữa hai biệt thự. Giữa hai biệt thự bất kỳ luôn tồn tại đường đi thông qua một số đoạn đường.

Công ty xây dựng cầu đường VINTRA trúng thầu nâng cấp hệ thống giao thông của khu đô thị VINNEXT với \(M\) gói thầu khác nhau. Mỗi gói thầu \(M_i\) được xác định bởi bộ ba số \((x_i, y_i, z_i)\) và được hiểu là sẽ nâng cấp các đoạn đường trên đường đi đơn (đường đi đơn là không có đoạn đường nào đi lặp lại) từ biệt thự \(x_i\) đến biệt thự \(y_i\) và được sử dụng biệt thự \(z_i\) làm điểm tập kết vật liệu. Việc thực hiện gói thầu \(M_i\) sẽ gây ảnh hưởng tới những biệt thự nằm trên đường đi đơn từ biệt thự \(x_i\) đến biệt thự \(y_i\) (kể cả chính hai biệt thự \(x_i\) và \(y_i\)), mức độ chịu ảnh hưởng của mỗi biệt thự khi thực hiện gói thầu này chính là khoảng cách từ biệt thự đó tới điểm tập kết vật liệu \(z_i\) (khoảng cách là số đoạn đường trên đường đi đơn từ biệt thự đó đến \(z_i\)).

Yêu cầu

Bạn biết trước \(M\) gói thầu, hãy tính tổng mức độ chịu ảnh hưởng của mỗi biệt thự khi thực hiện \(M\) gói thầu này.

Dữ liệu

Cho trong tệp VINNEXT.INP có cấu trúc:

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N, M \le 3 \times 10^5\)) lần lượt là số biệt thự và số gói thầu.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) cho biết có đoạn đường hai chiều nối giữa hai biệt thự \(x\) và \(y\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i, y_i, z_i\) (\(1 \le x_i, y_i, z_i \le N\)) mô tả gói thầu \(M_i\).

Kết quả

Ghi ra tệp VINNEXT.OUT một dòng gồm \(N\) số nguyên cách nhau một dấu cách, số thứ \(i\) là tổng mức độ chịu ảnh hưởng của biệt thự \(i\).

Ví dụ

VINNEXT.INP

6 2
1 2
1 3
3 4
3 5
5 6
2 6 4
4 5 1

VINNEXT.OUT

2 3 2 2 4 3

Giải thích: Tổng mức độ chịu ảnh hưởng của các biệt thự được mô tả như bảng sau:

Ràng buộc

• Subtask 1 (25% số test tương ứng 25% số điểm): \(N, M \le 10^3\).
• Subtask 2 (25% số test tương ứng 25% số điểm): mỗi biệt thự nối trực tiếp với không quá 2 biệt thự khác.
• Subtask 3 (25% số test tương ứng 25% số điểm): mọi gói thầu \(i\) đều có biệt thự \(z_i\) nằm trên đường đi đơn từ \(x_i\) đến \(y_i\).
• Subtask 4 (25% số test tương ứng 25% số điểm): không có ràng buộc gì thêm.