Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Berland Traffic

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBerland 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.

Input

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.

Output

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 22:18:05 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|