Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Vùng đất Trung địa đang đứng trước một âm mưu xâm lược của lũ quái vật. Bọn chúng đang đóng quân, xây thành gần vùng đất Trung địa. Nhà vua quyết định mở cuộc tấn công chớp nhoáng trước, làm cho quân địch suy yếu để tự rút lui, tránh gây thiệt hại cho dân chúng của đất nước.

Thông tin do thám báo về, quân địch đang đóng quân ở các pháo đài mới được xây dựng. Bọn quân địch đã tạo ra một loại vũ khí có sức mạnh khủng khiếp, sử dụng một nguồn năng lượng bí ẩn. Đội trinh thám nhận thấy rằng, bọn chúng đã đào một số đường hào giao thông 2 chiều đặc biệt, để trong tình trạng khẩn cấp, các pháo đài có hào giao thông liên kết với nhau, sẽ chuyển tất cả nguồn năng lượng đặc biệt ngay lập tức sang để bảo vệ cho pháo đài bị tấn công. Đồng thời, mỗi ngày, sẽ có các đội quân đi 1 chiều từ pháo đài này tới pháo đài khác, mang theo nguồn năng lượng đặc biệt tới pháo đài đó. Quân địch luân chuyển nguồn năng lượng bí ẩn liên tục trong hệ thống các pháo đài. Thật là khó để xác định nguồn năng lượng ở mỗi pháo đài là bao nhiêu?

Nhà vua yêu cầu tấn công vào pháo đài yếu nhất, để quyết dành chiến thắng trong trận đánh đầu tiên. Các tướng quân đã đánh giá sức mạnh của một pháo đài bằng số năng lượng ở pháo đài đó, cộng với số năng lượng của các pháo đài có hào giao thông liền kề.

Tuy nhiên, để di chuyển quân đội tới nơi đóng quân của quân địch cần mất t ngày. Các bạn hãy tìm xem pháo đài nào có sức mạnh yếu nhất để quân đội nhà vua sẽ tấn công vào?

Input

Dòng đầu tiên là số lượng bộ test T (1 <= T <= 10).

Mỗi test gồm, dòng đầu tiên là số nguyên n (1 <= n <= 100) là số pháo đài, số nguyên m (0 <= m <= (n-1)^2) là tổng số hào giao thông, và t (0 <= t <= 5000) là thời gian cần di chuyển tới nơi đóng quân của quân địch. Các pháo đài được đánh số từ 0, 1, 2 ... tới n-1.

Dòng thứ 2 gồm n số thực a_0, a_1, ..., a_[n-1] (0 <= a_i <= 1000) là số năng lượng bí ẩn có trong mỗi pháo đài tại thời điểm ban đầu.

m dòng tiếp theo, mỗi dòng gồm 2 số nguyên u_i, v_i, và số thực p_i (0 <= p_i < 1), thể hiện có hào giao thông liên kết giữa pháo đài u_i và pháo đài v_i, và p_i là tỉ lệ số năng lượng của pháo đài u_i sẽ luân chuyển sang pháo đài v_i mỗi ngày.

Output

Với mỗi test, in ra giá trị sức mạnh của pháo đài yếu nhất bên địch để tấn công, sai số không quá 10^-6.

Example

Input:
3
4 3 1
100 200 10 305
0 1 0.25
1 2 0.1
2 0 0.75
4 3 1
100 200 10 312
0 1 0.25
1 2 0.1
2 0 0.75
4 4 5
100 200 300 400
0 1 0.2
1 2 0.2
2 3 0.3
3 0 0.2

Output:
305.000000000
310.000000000
659.879000000

Giải thích test 1:

Sự phân bố năng lượng bí ẩn của quân địch sau 1 ngày đầu tiên. Cả 3 pháo đài 1, 2, 3 
đều có sức mạnh bằng 310, và pháo đài 4 là pháo đài yếu nhất.