CF267C.Berland Traffic

Berland traffic is very different from traffic in other countries. The capital of Berland consists of n junctions and m roads. Each road connects a pair of junctions. There can be multiple roads between a pair of junctions. For each road we know its capacity: value c__i is the maximum number of cars that can drive along a road in any direction per a unit of time. For each road, the cars can drive along it in one of two direction. That it, the cars can't simultaneously move in both directions. A road's traffic is the number of cars that goes along it per a unit of time. For road (a__i, b__i) this value is negative, if the traffic moves from b__i to a__i. A road's traffic can be a non-integer number.

The capital has two special junctions — the entrance to the city (junction 1) and the exit from the city (junction n). For all other junctions it is true that the traffic is not lost there. That is, for all junctions except for 1 and n the incoming traffic sum equals the outgoing traffic sum.

Traffic has an unusual peculiarity in the capital of Berland — for any pair of junctions (x, y) the sum of traffics along any path from x to y doesn't change depending on the choice of the path. Such sum includes traffic along all roads on the path (possible with the "minus" sign, if the traffic along the road is directed against the direction of the road on the path from x to y).

Your task is to find the largest traffic that can pass trough the city per one unit of time as well as the corresponding traffic for each road.

伯兰德的交通系统与其他国家截然不同。伯兰德首都由 $n$ 个路口和 $m$ 条道路组成。每条道路连接一对路口。任意两个路口之间可能存在多条道路。对每条道路，我们已知其容量：值 $c_i$ 表示单位时间内沿该道路任一方向所能通行的最多车辆数。对每条道路，车辆只能沿其中一个方向行驶，即不能同时在两个方向上通行。一条道路的“流量”指单位时间内沿该道路通行的车辆数。对道路 $(a_i,\,b_i)$，若流量实际从 $b_i$ 流向 $a_i$，则该流量取负值。道路的流量可以是非整数值。

首都包含两个特殊路口：城市入口（路口 1）和城市出口（路口 $n$）。对于其余所有路口，流量均不损失，即除路口 1 和 $n$ 外，每个路口的流入流量总和等于流出流量总和。

伯兰德首都的交通具有一个特殊性质：对任意一对路口 $(x,\,y)$，沿任意一条从 $x$ 到 $y$ 的路径上各条道路流量之和，与所选路径无关。该和包括路径上所有道路的流量（若某条道路上的实际流量方向与该路径从 $x$ 到 $y$ 的方向相反，则该项以负号计入）。

你的任务是求出单位时间内能够通过该城市的最大流量，以及此时每条道路对应的流量值。

The first line contains a positive integer n — the number of junctions (2 ≤ n ≤ 100). The second line contains integer m (1 ≤ m ≤ 5000) — the number of roads. Next m lines contain the roads' descriptions. Each road contains a group of three numbers a__i, b__i, c__i, where a__i, b__i are the numbers of junctions, connected by the given road, and c__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i; 0 ≤ c__i ≤ 10000) is the largest permissible traffic along this road.

第一行包含一个正整数 $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 \neq b_i$；$0 \leq c_i \leq 10000$）是该道路上允许的最大车流量。

In the first line print the required largest traffic across the city. Then print m lines, on each line print the speed, at which the traffic moves along the corresponding road. If the direction doesn't match the order of the junctions, given in the input, then print the traffic with the minus sign. Print the numbers with accuracy of at least five digits after the decimal point.

If there are many optimal solutions, print any of them.

第一行输出城市中所需的最大交通流量。随后输出 $m$ 行，每行输出对应道路上的车流速度。若车流方向与输入中给出的路口顺序不一致，则在该速度前添加负号。所有数字需保留至少小数点后五位有效数字。

若存在多个最优解，输出任意一个即可。