Cho đơn đồ thị bao gồm ~N~ đỉnh và ~M~ cạnh, các đỉnh được đánh số từ ~1~ đến ~N~, các cạnh được đánh số từ ~1~ đến ~M~. Các màu sắc dùng để tô các đỉnh của đồ thị được đánh số từ ~0~.

Ban đầu, mỗi đỉnh của đồ thị đều được tô màu ~0~. Thực hiện lần lượt ~Q~ thao tác như sau:

• Mỗi thao tác có dạng V D C : tiến hành tô màu ~C~ cho các đỉnh có độ dài đường đi ngắn nhất đến đỉnh ~V~ không vượt quá ~D~ ~(~lưu ý rằng các đỉnh này phải có ít nhất một đường đi đến đỉnh ~V)~.

Sau khi thực hiện thao tác, mỗi đỉnh sẽ mang màu mới nhất được tô.

Yêu cầu: Cho biết đồ thị và các thao tác. Bạn hãy xác định loại màu được tô cho mỗi đỉnh sau khi thực hiện tất cả ~Q~ thao tác.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \le N,M \le 2.10^5)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ mô tả cạnh thứ ~i~ nối hai đỉnh ~a_i-b_i~ ~(1 \le a_i,b_i \le N~, ~a_i \neq b_i)~.
• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 2.10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~V~, ~D~ và ~C~ mô tả thao tác ~(1 \le V \le N~, ~0 \le D \le 10~, ~1 \le C \le 2.10^5)~.

Output

• In ra ~N~ dòng, dòng thứ ~i~ chứa một số nguyên là màu của đỉnh thứ ~i~ sau khi thực hiện tất cả ~Q~ thao tác.

Examples

Sample Input

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

Sample Output

2
2
2
2
2
1
0

Scoring

• Subtask ~1~ ~-~ ~750~ điểm: ~N,M,Q \le 2000~
• Subtask ~2~ ~-~ ~750~ điểm: ~D \le 1~ với mọi thao tác
• Subtask ~3~ ~-~ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Ở ví dụ, quá trình thực hiện các thao tác được mô tả như trong hình sau: