N students of one university took part
in the Yekaterinozavodsk training camp.
When they returned home, it turned out that they had spent much of their own money for the
tickets to Yekaterinozavosk and back, for their lodgings, food and registration fees.
The students came to the dean of their department and asked him to compensate the costs of the trip.
The dean listened to them carefully and gave some amounts of money (possibly different) to all of them.
The next day two of these students came to the dean and told that
the two of them had been given A1 rubles
less than they had spent jointly. On the next day, the situation repeated itself:
a pair of students claimed that the dean owed them A2 rubles.
The situation repeated itself for a few days more. Finally, on the
M-th day a pair of students told the dean that
they two had spent together AM rubles more than
the dean had paid them. After that, the students lost any hope and stopped visiting the dean.
Then the dean took the notes with the students' demands and decided to calculate
how much he owed each of them.
But it turned out to be not so easy!
The first line contains integers N and M separated by a space (2 ≤ N ≤ 1000; 1 ≤ M ≤ 100000).
The following M lines contain the demands of pairs of students who visited the dean. The (i + 1)-st line
contains three integers separated by spaces: the numbers of two students who visited the dean on the i-th day and
the amount of money Ai they asked for. The students are numbered from 1 to N.
The number Ai is an integer in range from −10000 to 10000. A negative number neans that the students got from
the dean more that they spent. It is known that no pair of students visited the dean more than once.
If the dean can determine uniquely how much money he owes each of the students, write these sums with two digits
after the decimal point: in the i-th line output the amount he owes the i-th student. The numbers can
be negative; this means that the student owes the dean (sometimes it happens!). If it is impossible to
find these amounts, output “IMPOSSIBLE”.
1 2 2
2 3 4
3 1 6
1 2 2
1 3 4
1 4 6
Problem Author: Alexey Efremov
Problem Source: USU Junior Contest, October 2007