P6938 [ICPC 2017 WF] Son of Pipe Stream

两年以前，你帮助你的家乡安装了国内的第一个 Flubber 管道网络，获得了巨大成功。投票表明每个人都喜欢在自己家的厨房里装上 Flubber 分配器，而现在一些有进取心的市民发现了一种新的用途——Flubber 和水混合后似乎可以帮助灭火！这是一个很及时的发现，因为最近无法控制的大火出奇地常见。 你家乡的市议会想在一个位于中央的地方制造 Flubber 和水的混合物以利用 Flubber 的这个属性。这个被称为 Flubber 部门的地方拥有专门训练的员工去往着火的地点并且利用经过处理的 Flubber 来控制火势。 管道已经在城市中铺设好。你会得到管道布局，而你需要决定如何将 Flubber 从 Flubber 工厂、将水从一个本地水源通过管道运送至 Flubber 部门。 注意 Flubber 和水会在同一管道网络中，甚至可能在同一条管道中流动。所有管道是双向的，但是 Flubber 和水不能在同一条管道中异向流动。此外，如果两种液体同向流过一条管道，它们会不可避免地混合，因此网络中的所有节点配备了特殊的膜和筛，如你所见，可以分离和重新组织所有流入的混合物。管道网络是个封闭系统，因此在每个节点处每种液体的总流入速率必须等于总流出速率，除了每种液体各自的源头和目的地（Flubber 部门）。 每条管道有某个容量，有些粘稠的 Flubber 有一个粘度值 $v$，所以能运输 $v$ 升每秒的水的管道只能运输 $1$ 升每秒的 Flubber。管道对于混合物的容量是线性变化的。更精确地，假设 $c$ 表示管道对于水的容量，$f$ 和 $w$ 分别表示 Flubber 和水流过管道的速率（单位均为升每秒），则容量的限制用不等式 $v⋅f+w\le c$ 表示。 你主要关心的是平衡流到 Flubber 部门的混合物。你想要尽可能多的混合液体，但是也需要足够的水——因为未经稀释的 Flubber 是高度易燃的——也需要足够的 Flubber——因为 Flubber 部门可不能没了 Flubber！你想出了一个公式来衡量最终混合物的价值：$F^a⋅W^{1-a}$，其中 $F$ 是以升每秒为单位的 Flubber 的流入速率，$W$ 是以升每秒为单位的水的流入速率，$a$ 是一个给定的介于 0 和 1 之间的常数。 求出 $F^a⋅W^{1−a}$ 能达到的最大值以及如何安排 Flubber 和水的路径来达到它。

输入的第一行包含地点的数量 $n (3\le n\le 300)$，管道的数量 $p (n-1\le p\le \frac12n(n -1))$，和实数 $v (1\le v\le 10)$ 和 $a (0.01\le a\le 0.99)$。地点从 1 到 $n$ 标号；1 是 Flubber 工厂，2 是水源，3 是 Flutter 部门。实数的小数点后最多有十位。 接下来的 $p$ 行每行描述了一条管道。每行有两个整数 $j$ 和 $k (1\le j < k\le n)$，表示管道连接的地点，和一个整数 $c (1\le c\le 10)$，表示这条管道的水容量，以升每秒为单位。 没有两条管道连接相同的两个地点，此外，还保证网络是连通的。

首先，对于每条管道（按照输入的顺序），输出两个值：其中 Flubber 流过的速率和其中水流过的速率 （如果从 k 流到 j 则为负数），使得 $F^a⋅W^{1−a}$ 最大化。然后输出其最大值，在 $10^{−4}$ 的绝对误差以内。 如果有多解，输出任意一种均可。所有限制（Flubber 和水没有在同一条管道内异向流动、流量守恒、管道容量以及构造的解和其声称的值的一致性）需要在 $10^{−4}$ 的绝对误差内满足。

Time limit: 5 s, Memory limit: 512 MB.