ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Dean's Debts

Time limit: 2.0 second
Memory limit: 64 MB
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”.


3 3
1 2 2
2 3 4
3 1 6
4 3
1 2 2
1 3 4
1 4 6
Problem Author: Alexey Efremov
Problem Source: USU Junior Contest, October 2007
To submit the solution for this problem go to the Problem set: 1580. Dean's Debts