Hai năm trước, bạn giúp lắp đặt mạng ống Flubber đầu tiên của cả nước tại quê nhà và đạt thành công lớn. Khảo sát cho thấy mọi người đều thích có máy cấp Flubber riêng trong bếp, và nay một vài cư dân năng động đã tìm ra công dụng cho nó. Hóa ra Flubber pha với nước có thể giúp dập lửa! Phát hiện này rất kịp thời vì gần đây các vụ cháy mất kiểm soát xảy ra thường xuyên đến bất ngờ.

Hội đồng thành phố muốn tận dụng đặc tính này bằng cách tạo hỗn hợp Flubber và nước tại một trạm ở trung tâm. Trạm có tên Flubber Department (FD) cũng sẽ có nhân viên chuyên trách được huấn luyện đến hiện trường cháy và dùng Flubber đã xử lý để khống chế lửa.

Đường ống đã được lắp khắp thành phố. Với sơ đồ ống cho trước, bạn phải xác định cách dẫn Flubber từ nhà máy và nước từ nguồn địa phương qua các ống đến FD.

Cả hai chất lỏng sẽ chảy trong cùng mạng ống, thậm chí có thể cùng một ống. Mọi ống đều hai chiều, nhưng Flubber và nước không thể chảy ngược chiều trong cùng ống. Nếu cùng chiều trong cùng ống, chúng chắc chắn hòa trộn. Vì vậy các nút có màng và bộ lọc đặc biệt để bạn tùy ý tách và phối trộn lại mọi hỗn hợp chảy vào. Mạng là hệ kín: tổng lưu lượng mỗi chất lỏng vào một nút phải bằng tổng lưu lượng chất đó ra khỏi nút, trừ tại nguồn của chất đó và đích, FD.

Mỗi ống có một dung lượng nhất định. Flubber khá sánh, có độ nhớt $v$, nên ống vận chuyển được $v$ lít nước mỗi giây chỉ vận chuyển được $1$ lít Flubber mỗi giây. Dung lượng thay đổi tuyến tính đối với hỗn hợp hai chất. Cụ thể, nếu $c$ là dung lượng đối với nước, còn $f,w$ là lưu lượng Flubber và nước, tất cả tính bằng lít mỗi giây, thì ràng buộc là $v \cdot f + w \le c$.

Mối quan tâm chính là cân bằng hỗn hợp đến FD. Bạn muốn tổng lượng chất lỏng càng lớn càng tốt, nhưng cũng cần đủ nước vì Flubber nguyên chất rất dễ cháy, và đủ Flubber vì thiếu nó thì khó gọi là “Flubber Department”! Bạn đã nghĩ ra công thức đo “giá trị” của hỗn hợp cuối: $F^a \cdot W^{1-a}$, trong đó $F,W$ là lưu lượng Flubber và nước chảy vào tính bằng lít mỗi giây, còn $a$ là hằng số cho trước nằm giữa $0$ và $1$.

Hãy xác định giá trị lớn nhất có thể đạt của $F^a \cdot W^{1-a}$ và cách dẫn hai chất lỏng để đạt được giá trị đó.

Dữ liệu vào

Dòng đầu chứa số địa điểm $n$ ($3 \le n \le 200$), số ống $p$ ($n-1 \le p \le \frac12 n(n-1)$), và các số thực $v$ ($1 \le v \le 10$), $a$ ($0.01 \le a \le 0.99$). Các địa điểm được đánh số từ $1$ đến $n$: $1$ là nhà máy Flubber, $2$ là nguồn nước, $3$ là FD. Các số thực có nhiều nhất $10$ chữ số sau dấu thập phân.

Mỗi dòng trong $p$ dòng tiếp theo mô tả một ống. Mỗi dòng chứa hai số nguyên $j,k$ ($1 \le j < k \le n$), các địa điểm được nối, và số nguyên $c$ ($1 \le c \le 10$), dung lượng đối với nước tính bằng lít mỗi giây.

Không có hai ống nối cùng một cặp địa điểm. Ngoài ra, bảo đảm mạng liên thông.

Dữ liệu ra

Trước tiên, với mỗi ống theo thứ tự trong dữ liệu vào, in hai giá trị: lưu lượng Flubber và lưu lượng nước qua nó, mang dấu âm nếu chất lỏng chảy từ $k$ đến $j$, sao cho $F^a \cdot W^{1-a}$ lớn nhất. Sau đó in giá trị lớn nhất này với sai số tuyệt đối không quá $10^{-4}$.

Nếu có nhiều lời giải, bất kỳ lời giải nào cũng được chấp nhận. Mọi ràng buộc —không cho hai chất chảy ngược chiều trong cùng ống, bảo toàn lưu lượng, dung lượng ống, và sự nhất quán giữa lời giải xây dựng với giá trị khai báo— phải được thỏa mãn trong sai số tuyệt đối $10^{-4}$.

Ví dụ

Dữ liệu vào 1

6 6 3.0 0.66
2 4 8
4 6 1
3 6 1
4 5 5
1 5 7
3 5 3

Dữ liệu ra 1

0.000000000 1.360000000
0.000000000 1.000000000
0.000000000 -1.000000000
0.000000000 0.360000000
0.880000000 0.000000000
-0.880000000 -0.360000000
1.02037965897

Dữ liệu vào 2

5 5 1.0 0.5
1 2 10
2 3 10
3 4 10
4 5 10
3 5 10

Dữ liệu ra 2

5 0
5 5
4.2 3.14159
4.2 3.14159
-4.2 -3.14159
5