CF653D.Delivery Bears

Niwel is a little golden bear. As everyone knows, bears live in forests, but Niwel got tired of seeing all the trees so he decided to move to the city.

In the city, Niwel took on a job managing bears to deliver goods. The city that he lives in can be represented as a directed graph with n nodes and m edges. Each edge has a weight capacity. A delivery consists of a bear carrying weights with their bear hands on a simple path from node 1 to node n. The total weight that travels across a particular edge must not exceed the weight capacity of that edge.

Niwel has exactly x bears. In the interest of fairness, no bear can rest, and the weight that each bear carries must be exactly the same. However, each bear may take different paths if they like.

Niwel would like to determine, what is the maximum amount of weight he can deliver (it's the sum of weights carried by bears). Find the maximum weight.

尼维尔是一只小金熊。众所周知，熊生活在森林里，但尼维尔看腻了所有的树，于是决定搬到城市居住。

在城市中，尼维尔找了一份工作，负责管理熊来运送货物。他所居住的城市可以表示为一个具有 $n$ 个节点和 $m$ 条有向边的有向图。每条边都有一个权重容量。一次运送任务由一只熊沿从节点 $1$ 到节点 $n$ 的一条简单路径，用手携带一定重量的货物完成。经过某条边的所有货物的总重量不得超过该边的权重容量。

尼维尔恰好有 $x$ 只熊。出于公平起见，不允许任何一只熊休息，且每只熊所携带的重量必须完全相同。不过，每只熊可以选择不同的路径（如果它们愿意的话）。

尼维尔希望确定：他最多能运送多少总重量（即所有熊所携带重量之和）。请找出这个最大总重量。

The first line contains three integers n, m and x (2 ≤ n ≤ 50, 1 ≤ m ≤ 500, 1 ≤ x ≤ 100 000) — the number of nodes, the number of directed edges and the number of bears, respectively.

Each of the following m lines contains three integers a__i, b__i and c__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ c__i ≤ 1 000 000). This represents a directed edge from node a__i to b__i with weight capacity c__i. There are no self loops and no multiple edges from one city to the other city. More formally, for each i and j that i ≠ j it's guaranteed that a__i ≠ a__j or b__i ≠ b__j. It is also guaranteed that there is at least one path from node 1 to node n.

第一行包含三个整数 $n$、$m$ 和 $x$（$2 \leq n \leq 50$，$1 \leq m \leq 500$，$1 \leq x \leq 100\,000$），分别表示节点数、有向边数和熊的数量。

接下来的 $m$ 行中，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$，$1 \leq c_i \leq 1\,000\,000$）。这表示一条从节点 $a_i$ 指向节点 $b_i$ 的有向边，其容量为 $c_i$。图中不存在自环，也不存在两个节点之间重复的有向边。更严格地说，对任意 $i \neq j$，保证 $a_i \neq a_j$ 或 $b_i \neq b_j$。此外，保证至少存在一条从节点 $1$ 到节点 $n$ 的路径。

Print one real value on a single line — the maximum amount of weight Niwel can deliver if he uses exactly x bears. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if .

在单独一行中输出一个实数值——Niwel 恰好使用 x 只熊时所能运送的最大重量。若你的答案的绝对误差或相对误差不超过 10 - 6，则视为正确。

具体而言：假设你的答案为 a，评测组的答案为 b。当且仅当 时，评测程序将判定你的答案正确。

In the first sample, Niwel has three bears. Two bears can choose the path , while one bear can choose the path . Even though the bear that goes on the path can carry one unit of weight, in the interest of fairness, he is restricted to carry 0.5 units of weight. Thus, the total weight is 1.5 units overall. Note that even though Niwel can deliver more weight with just 2 bears, he must use exactly 3 bears on this day.

在第一个样例中，Niwel 有三只熊。其中两只熊可以选择路径 ，另一只熊可以选择路径 。尽管走路径 的那只熊本可承载 1 单位重量，但为了公平起见，其承载量被限制为 0.5 单位重量。因此，总承载重量为 1.5 单位。注意：尽管 Niwel 仅用 2 只熊即可运送更多重量，但他当天必须恰好使用 3 只熊。