Cho một mạng đối xứng có ~n~ đỉnh, mỗi cạnh của mạng có một khả năng thông qua và một cước phí vận chuyển nhất định (như nhau theo cả hai chiều). Cho trước một lượng hàng ~S~ cần vận chuyển từ đỉnh nguồn (đánh số là ~s~) tới đỉnh đích (đánh số là ~f~). Hãy tìm một phương án vận chuyển, nghĩa là hãy xác định trên mỗi cạnh của mạng cần vận chuyển bao nhiêu hàng, theo chiều nào, sao cho phù hợp với khả năng thông qua của mạng (trên mỗi cạnh lượng hàng vận chuyển không vượt quá khả năng thông qua của cạnh) và vận chuyển được lượng hàng ~S~ từ nguồn về đích với tổng chi phí vận chuyển là nhỏ nhất.

Về mặt toán học, bài toán tìm luồng với chi phí nhỏ nhất có thể diễn đạt như sau:

Cực tiểu hóa hàm chi phí ~\sum{c_{ij} \times x_{ij}}~ với điều kiện:

1. ~\sum{\left(x_{ij} - x_{ji}\right)}~ với ~j = 1 \dots n~, có giá trị

   • ~S~ nếu ~i = s~
   • ~0~ nếu ~i \ne s~; ~i \ne n~
   • ~-S~ nếu ~i = f~

2. ~0 \leq x_{ij} \leq d_{ij}~ với mọi cạnh ~\left(i, j\right)~

Ở đây đỉnh nguồn được đánh số là ~s~, đỉnh đích là ~f~, ~c_{ij}~ là chi phí vận chuyển một đơn vị hàng trên cạnh ~\left(i, j\right)~, ~d_{ij}~ là khả năng thông qua của cạnh ~\left(i, j\right)~; còn ~x_{ij}~ là khối lượng hàng vận chuyển trên cạnh ~\left(i, j\right)~ cần xác định.

Input

• Dòng đầu là ~n, m, k, s, f~ : Số đỉnh, số đường, số đơn vị hàng cần vận chuyển. đỉnh bắt đầu, đỉnh kết thúc
• ~m~ dòng tiếp theo mỗi bao gồm ~u, v, c, d~ cho biết có đường 2 chiều từ ~u~ đến ~v~ với chi phí là ~c~ và khả năng thông qua là ~d~.

Dữ liệu được cho đảm bảo mỗi cạnh chỉ xuất hiện nhiều nhất một lần.

Output

• Dòng đầu, nếu không vận chuyển được ghi ~-1~, nếu có ghi tổng chi phí vận chuyển.
• Nếu có nghiệm thì một số dòng tiếp ghi ~u, v, i~ cho biết vận chuyển ~i~ đơn vị hàng từ trên cạnh ~u~ đến ~v~. Kết thúc bằng "~0~ ~0~ ~0~".

Giới hạn

• ~n \leq 100~
• ~d_{ij} \leq 30000~
• ~c_{ij} \leq 10^{9}~

Phạm vi tính toán là số nguyên ~32-bit~ có dấu.

Sample Input

6 8 5 1 6
1 2 1 2
1 4 3 4
2 3 1 4
2 5 5 2
3 4 2 4
3 6 1 2
4 6 4 1
5 6 6 2

Sample Output

43
1 2 2
1 4 3
2 5 2
4 3 2
3 6 2
4 6 1
5 6 2
0 0 0