Niwel 是一只小金熊。众所周知,熊生活在森林里,但尼维尔厌倦了看到所有的树木,所以他决定搬到城市去。
在城里,尼维尔承担了一份管理熊送货的工作。他居住的城市可以表示为一个有 n 个节点和 m 个边的有向图。每条边都有一个承重能力。一次交付由一只熊用熊的手在从节点 1 到节点 n 的简单路径上搬运重量组成。穿过特定边缘的总重量不得超过该边缘的承重能力。
Niwel 正好有 x 只熊。为了公平起见,没有一只熊可以休息,每只熊所承载的重量必须完全相同。然而,如果每只熊愿意的话,他们可能会走不同的路。
Niwel 想确定他能承受的最大重量是多少(这是熊所承受重量的总和)。求最大重量。
输入
第一行包含三个整数 n、m 和 x (2 ≤ n ≤ 50, 1 ≤ m ≤ 500, 1 ≤ x ≤ 100 000)——分别是节点数、有向边数和熊数。
以下 m 行每行包含三个整数 ai、bi 和 ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 1 000 000)。这表示从节点 ai 到 bi 的有向边,其权重容量为 ci。从一个城市到另一城市不存在自环,也不存在多重边。更正式地说,对于每个 i 和 j,i ≠ j,可以保证 ai ≠ aj 或 bi ≠ bj。还保证从节点1到节点n至少有一条路径。
输出
在一行上打印一个实际值——如果 Niwel 正好使用 x 只熊,他可以提供的最大重量。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
4 4 3 1 2 2 2 4 1 1 3 1 3 4 2
输出 #1
1.5000000000
输入 #2
5 11 23 1 2 3 2 3 4 3 4 5 4 5 6 1 3 4 2 4 5 3 5 6 1 4 2 2 5 3 1 5 2 3 2 30
输出 #2
10.2222222222
注意
在第一个示例中,Niwel 有三只熊。两只熊可以选择路径 $$1 \rightarrow 3 \rightarrow 4$$,而一只熊可以选择路径 $$1 \rightarrow 2 \rightarrow 4$$。尽管走在 $$1 \rightarrow 2 \rightarrow 4$$ 路径上的熊可以承载 1 个单位的重量,但为了公平起见,他只能承载 0.5 个单位的重量。因此,总重量为 1.5 个单位。请注意,尽管 Niwel 只需要 2 只熊就可以提供更多的重量,但他在这一天必须使用 3 只熊。