There are N stations on a certain railway line, which are sequentially numbered from 1 to N. The distances between some stations are known. It is required to accurately calculate the lengths of all hauls between neighboring stations or indicate that this is impossible (that is, the information provided is contradictory or insufficient).
Input
The input file contains the numbers N — number of stations (2 ≤ N ≤ 100) and E — the number of pairs of stations, the distances between which are given (0 ≤ E ≤ 10000). Next comes E triples of numbers, the first two numbers of each triple set the station numbers (these are numbers from the range from 1 to N), and the third — the distance between these stations (all these distances are specified exactly and are expressed as real non-negative numbers with no more than 3 digits after the decimal point).
Imprint
In the case when it is possible to restore the lengths of the stages unambiguously, first print the number 1, and then N–1 real number into the output file. The first of these numbers should correspond to the distance from the 1st station to the 2nd, the second — from 2nd to 3rd, and so on. All numbers must be displayed with an accuracy of 3 digits after the decimal point.
If the given information about distances between stations is inconsistent or does not allow you to unambiguously accurately restore the lengths of hauls, output a single number 2 to the output file.
Examples
| # |
Input |
Output |
| 1 |
2 3
1 1 0
2 2 0
2 1 2.5
| 1
2.500 |
| 2 |
15 13
1 2 1
1 3 2
1 4 3
1 5 4
1 6 5
1 7 6
1 8 7
1 9 8
1 10 9
1 11 10
1 12 11
1 13 12
15 14 13
| 2 |