Gấu giao hàng

Một thành phố được mô hình hoá bằng đồ thị có hướng gồm $n$ đỉnh và $m$ cạnh. Mỗi cạnh có một sức chứa trọng lượng $c_i$ — tổng trọng lượng đi qua cạnh đó không được vượt quá $c_i$.

Có đúng $x$ con gấu giao hàng. Mỗi con gấu phải đi từ đỉnh $1$ đến đỉnh $n$ theo một đường đi đơn (không lặp đỉnh) và mang đúng cùng một trọng lượng $w$. Các con gấu khác nhau có thể chọn các đường đi khác nhau. Không con gấu nào được nghỉ — tất cả $x$ con đều phải tham gia.

Hãy tìm giá trị tổng trọng lượng lớn nhất mà $x$ con gấu có thể vận chuyển cùng nhau, tức là $x·w$ với $w$ lớn nhất có thể sao cho tồn tại cách phân $x$ con gấu vào các đường đi $1\to n$ mà mọi cạnh đều thoả ràng buộc sức chứa.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$, $m$, $x$ — số đỉnh, số cạnh và số con gấu.

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$, $c_i$ mô tả một cạnh có hướng từ $a_i$ đến $b_i$ với sức chứa $c_i$.

Đảm bảo: không có cạnh tự nối (loop) và không có hai cạnh trùng hướng giữa cùng một cặp đỉnh. Luôn tồn tại ít nhất một đường đi từ đỉnh $1$ đến đỉnh $n$.

Dữ liệu ra

In ra một số thực — tổng trọng lượng tối đa có thể vận chuyển. Đáp án của bạn được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án chuẩn không vượt quá ${10}^{-6}$.

Ràng buộc

• $2\le n\le 50$
• $1\le m\le 500$
• $1\le x\le 100000$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$
• $1\le c_i\le {10}^6$

Ví dụ