Cho đơn đồ thị vô hướng gồm N đỉnh (các đỉnh được đánh số từ 1 đến \(N\)), và có M cạnh. Tất cả \(M\) cạnh này đều có màu xanh và trọng số bằng \(a\).

Người ta thực hiện thêm vào đồ thị các cạnh màu đỏ có trọng số \(b\) nối tất cả các cặp đỉnh \(u,v\) thỏa mãn các điều kiện sau:

• Chưa có cạnh nối giữa hai đỉnh \(u,v;\)

• Đường đi ngắn nhất (chỉ qua các cạnh màu xanh) từ đỉnh \(u\) đến đỉnh \(v\) gồm đúng hai cạnh.

Sau khi thực hiện thêm cạnh đỏ, hãy xác định độ dài đường đi ngắn nhất (không quan trọng màu sắc của cạnh) từ một đỉnh \(S\) đến tất cả các đỉnh của đồ thị.

Trong bài này, bạn cần phải trả lời T truy vấn như vậy.

Dữ liệu

• Dòng đầu tiên: gồm một số nguyên \(T (1≤T≤5)\) là số truy vấn cần trả lời; \

• Tiếp theo là \(T\) truy vấn, mỗi truy vấn gồm:

  • Dòng đầu tiên của truy vấn ghi năm số nguyên \(N,M,S,a,b (2≤N≤10^5;1≤M≤10^5;1≤a,b≤10^3 );\)

    _ Dòng 2,3,..,M+1 của truy vấn: mỗi dòng ghi hai số nguyên \(u,v\) mô tả một cạnh xanh nối giữa hai đỉnh u,v. Dữ liệu đảm bảo có đường đi toàn cạnh xanh từ đỉnh \(S\) đến tất cả các đỉnh của đồ thị.

Kết quả

• Với mỗi truy vấn, ghi trên N dòng, mỗi dòng gồm một số nguyên tương ứng với đường đi ngắn nhất từ đỉnh \(S\) tới tất cả các đỉnh của đồ thị. Xem ví dụ để hiểu rõ hơn.

Ràng buộc

• 30% \(N,M≤700\)

• 70% Không có ràng buộc bổ sung

Sample Input

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

Sample Output

0
3
3
2
5