Cho một đồ thị vô hướng gồm đỉnh và cạnh. Các đỉnh được đánh số từ tới . Mỗi đỉnh và mỗi cạnh của đồ thị đều có trọng số. Trọng số của đỉnh thứ là . Cạnh thứ của đồ thị nối hai đỉnh và có trọng số là . Đồ 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à đi qua các cạnh . 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 và trên đồ thị, gọi là trọng số nhỏ nhất của một đường đi từ đến . Nếu , ta có . Với mỗi đỉnh của đồ thị, hãy tính .
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên là số thứ tự của subtask chứa test này;
Dòng thứ hai chứa hai số nguyên và lần lượt là số đỉnh và số cạnh của đồ thị.
Dòng thứ ba chứa số nguyên lần lượt là trọng số của các đỉnh.
dòng cuối cùng, dòng thứ chứa ba số nguyên và cho biết có một cạnh của đồ thị nối hai đỉnh và có trọng số là . Dữ liệu vào đảm bảo đồ thị này liên thông.
Dữ liệu ra:
Một dòng duy nhất với số nguyên .
Ví dụ:
Dữ liệu vào:
4
3 3
5 6 3
1 2 22
2 3 7
3 1 97
Dữ liệu ra:
264 174 174
Giải thích:
Trong ví dụ trên, ta có:
;
;
$d(3, 1) = d(1, 3) = 22 * 6 = 132.
Giới hạn:
Subtask số điểm có tất cả các đỉnh và tất cả các cạnh đều có trọng số bằng ;
Subtask số điểm có tất cả các đỉnh có trọng số bằng ;
Subtask số điểm có tất cả các cạnh có trọng số bằng ;
