You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 ci 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 (ai, bi) this value is negative, if the traffic moves from bi to ai. 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.

## Input Format
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 ai, bi, ci, where ai, bi are the numbers of junctions, connected by the given road, and ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 10000) is the largest permissible traffic along this road.

## Output Format
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.

## Examples
```input
2
3
1 2 2
1 2 4
2 1 1000
```
```output
6.00000
2.00000
2.00000
-2.00000
```
-----
```input
7
11
1 2 7
1 2 7
1 3 7
1 4 7
2 3 7
2 5 7
3 6 7
4 7 7
5 4 7
5 6 7
6 7 7
```
```output
13.00000
2.00000
2.00000
3.00000
6.00000
1.00000
3.00000
4.00000
7.00000
1.00000
2.00000
6.00000
```

Now solve the problem and return the code.