Đồ thị

Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) tới \(n\). Mỗi đỉnh và mỗi cạnh của đồ thị đều có trọng số. Trọng số của đỉnh thứ \(i\) là \(w_{i}\). Cạnh thứ \(j\) của đồ thị nối hai đỉnh \(f_{j}\) và \(t_{j}\) có trọng số là \(c_{j}\). Đồ thị được đảm bảo là liên thông, nói cách khác, luôn tồn tại đường đi giữa hai đỉnh bất kỳ của đồ thị.

Xét một đường đi bất kỳ trên đồ thị, giả sử đường đi đi qua các đỉnh \(v_{1}, v_{2}, ..., v_{k}\) và đi qua các cạnh \(e_{1}, e_{2}, ..., e_{l}\). Khi đó, ta định nghĩa trọng số của đường đi này là \(max(w_{v_{1}}, w_{v_{2}}, ..., w_{v_{k}})·max(c_{e_{1}}, c_{e_{2}}, ..., c_{e_{l}})\). Nói cách khác, trọng số của một đường đi là tích của
trọng số lớn nhất của một đỉnh trên đường đi (bao gồm đỉnh xuất phát và đỉnh kết thúc) và trọng số lớn nhất của một cạnh trên đường đi.

Với hai đỉnh \(u\) và \(v\) trên đồ thị, gọi \(d(u, v)\) là trọng số nhỏ nhất của một đường đi từ \(u\) đến \(v\). Nếu \(u = v\), ta có \(d(u, v) = 0\). Với mỗi đỉnh \(u\) của đồ thị, hãy tính \(S(u) = d(u, 1) + d(u, 2) + ... + d(u, n)\).

Input

Dòng đầu tiên chứa số nguyên \(θ\) \((1 ≤ θ ≤ 5)\) là số thứ tự của subtask chứa test này.

Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 500, n - 1 \leq m \leq n\cdot(n - 1) / 2)\) lần lượt là số đỉnh và số cạnh của đồ thị.

Dòng thứ ba chứa \(n\) số nguyên \(w_{1}, w_{2}, ..., w_{n}\) \((1 ≤ w_{i} ≤ 10^7)\) lần lượt là trọng số của các đỉnh.

\(m\) dòng cuối cùng, dòng thứ \(j\) chứa ba số nguyên \(f_{j}\), \(t_{j}\) và \(c_{j}\) \((1 ≤ f_{j}, t_{j} ≤ n, 1 ≤ c_{j} ≤ 10^7)\) cho biết có một cạnh của đồ thị nối hai đỉnh \(f_{j}\), \(t_{j}\) và có trọng số là \(c_{j}\). Dữ liệu vào đảm bảo đồ thị này liên thông.

Output

Một dòng duy nhất với \(n\) số nguyên \(S(1)\), \(S(2)\), ..., \(S(n)\).

Example

4
3 3
5 6 3
1 2 22
2 3 7
3 1 97

264 174 174 

Scoring

Subtask \(1\) (\(14\) điểm): Tất cả các đỉnh và tất cả các cạnh đều có trọng số bằng \(1\).

Subtask \(2\) (\(20\) điểm): Tất cả các đỉnh có trọng số bằng \(1\).

Subtask \(3\) (\(20\) điểm): Tất cả các cạnh có trọng số bằng \(1\).

Subtask \(4\) (\(20\) điểm): \(n ≤ 50\)

Subtask \(5\) (\(26\) điểm): Không có ràng buộc gì thêm.