Khu rừng FPTOJ có \(N\) cây và \(N-1\) con đường nối chúng. Mỗi con đường có độ dài \(w_i\).

Tèo muốn biết, đối với mỗi cây trong khu rừng, đường đi dài nhất đi qua cây đó có độ dài bao nhiêu. Nói cách khác, với mỗi đỉnh \(u\), tìm giá trị lớn nhất của \(dist(a, u) + dist(u, b)\) với \(a, b\) là hai đỉnh bất kỳ sao cho đường đi từ \(a\) đến \(b\) đi qua \(u\) (có thể \(a = u\) hoặc \(b = u\)).

Yêu cầu: Với mỗi đỉnh \(u\), in ra độ dài đường đi dài nhất đi qua \(u\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le w \le 10^6\)).

Đầu ra

• In ra \(N\) dòng, dòng thứ \(i\) là độ dài đường đi dài nhất đi qua đỉnh \(i\).

Ví dụ

Đầu vào:

4
1 2 5
2 3 10
2 4 7

Đầu ra:

15
17
17
17

Giải thích

• Đỉnh 1: đường đi qua 1 dài nhất là \(1 \to 2 \to 3\): \(5+10=15\).
• Đỉnh 2: đường đi qua 2 dài nhất là \(3 \to 2 \to 4\): \(10+7=17\).
• Đỉnh 3: đường đi qua 3 dài nhất là \(3 \to 2 \to 4\): \(10+7=17\).
• Đỉnh 4: đường đi qua 4 dài nhất là \(4 \to 2 \to 3\): \(7+10=17\).

Subtask