CF267C Berland Traffic

伯兰的交通与其他国家非常不同。伯兰的首都由 $n$ 个路口和 $m$ 条道路组成。每条道路连接一对路口。对于同一对路口，可能存在多条道路。每条道路都有其容量：$c_{i}$ 表示这条道路在任一方向上每单位时间内最多能通行的车辆数。每条道路上的车辆只能在两个方向中的一个方向通行，也就是说，车辆不能同时双向通行。道路的流量是每单位时间内通过该道路的车辆数。对于道路 $(a_{i},b_{i})$，如果流量是负数，则表示车辆由 $b_{i}$ 向 $a_{i}$ 行驶。道路的流量可以为非整数。 首都中有两个特殊路口——城市的入口（路口 $1$）和城市的出口（路口 $n$）。对于其他所有路口，流量不会在这些路口丢失。也就是说，除 $1$ 和 $n$ 以外的所有路口，流入流量之和等于流出流量之和。 伯兰首都的交通还有一个特别之处——对于任意一对路口 $(x,y)$，从 $x$ 到 $y$ 沿任意路径经过的所有道路的流量和是相同的，这与选择哪条路径无关。这个和包括了路径上所有道路的流量（如果流量方向与路径方向相反，则取负号）。 你的任务是求出每单位时间内可以通过城市的最大流量，以及每条道路上对应的流量。

第一行包含一个正整数 $n$，表示路口数（$2 \leq n \leq 100$）。 第二行包含一个整数 $m$，表示道路数（$1 \leq m \leq 5000$）。 接下来 $m$ 行，每行包含三个数 $a_{i}$、$b_{i}$、$c_{i}$，表示一条道路连接着路口 $a_{i}$ 和 $b_{i}$，且最大允许流量为 $c_{i}$（$1 \leq a_{i},b_{i} \leq n$；$a_{i} \ne b_{i}$；$0 \leq c_{i} \leq 10000$）。

第一行输出单位时间内能够通过城市的最大流量。 接下来 $m$ 行，第 $i$ 行输出第 $i$ 条道路上的流量（可为负数，若流向与输入顺序相反，则取负号）。请保证输出至少五位小数。 若最优解有多个，输出任意一种即可。

由 ChatGPT 5 翻译