Cho một đa đồ thị vô hướng liên thông gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\) và các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) nối đỉnh \(u_i\) với đỉnh \(v_i\) và có trọng số là \(w_i\). Giữa hai đỉnh có thể có một hoặc nhiều cạnh nối, và một đỉnh có thể có cạnh nối tới chính nó. Mỗi đỉnh của đồ thị được tô một màu, màu của đỉnh thứ \(i\) được thể hiện bởi số nguyên \(c_i\). Hai đỉnh \(x\) và \(y\) được tô cùng màu khi và chỉ khi \(c_x = c_y\).

Với hai đỉnh \(x\) và \(y\) bất kì trên đồ thị, ta định nghĩa giá trị \(d(x, y)\) như sau: Xét tất cả các đường đi có tổng trọng số nhỏ nhất từ \(x\) đến \(y\), ta chọn ra đường đi có số màu phân biệt của các đỉnh đi qua là nhỏ nhất. Giá trị \(d(x, y)\) chính là số màu phân biệt nhỏ nhất trên một đường đi ngắn nhất từ \(x\) đến \(y\) này.

Với mỗi đỉnh \(u\), gọi \(s_u = d(u, 1) + d(u, 2) + \ldots + d(u, n)\). Hãy tính \(s_u\) với mọi đỉnh \(u\) trên đồ thị.

Dữ liệu

Vào từ file văn bản color.inp:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq m < n \leq 4 \cdot 10^5)\), lần lượt là số đỉnh và số cạnh của đồ thị.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) \((1 \leq c_i \leq n)\) thể hiện màu của các đỉnh.
• Trong \(m\) dòng còn lại, mỗi dòng chứa ba số nguyên \(u_i\), \(v_i\) và \(w_i\) \((1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 227)\) thể hiện cạnh thứ \(i\) của đồ thị.

Kết quả

Ghi ra file văn bản color.out:

• In ra \(n\) số nguyên \(s_1, s_2, \ldots, s_n\). Các số được viết trên một dòng, phân cách nhau bởi dấu cách.

Ràng buộc

• Subtask \(1\) (\(5\) điểm): \(n \leq 10\)
• Subtask \(2\) (\(10\) điểm): \(n \leq 300\)
• Subtask \(3\) (\(15\) điểm): \(n \leq 5000\)
• Subtask \(4\) (\(15\) điểm): \(c_1 = c_2 = \ldots = c_n\)
• Subtask \(5\) (\(15\) điểm): Các số \(c_1, c_2, \ldots, c_n\) đôi một phân biệt.
• Subtask \(6\) (\(20\) điểm): Mỗi đỉnh kề với tối đa hai cạnh.
• Subtask \(7\) (\(20\) điểm): Không có ràng buộc gì thêm.

Ví dụ

5 4
1 2 3 2 3
1 2 9
2 3 7
2 4 2
1 5 2

10 9 11 9 12