Description

HZGD has just led his $N$ students to the LXX-th NOI. But his students realized that the expenses they should have been reimbursed are still overdue, so they all came to HZGD asking for reimbursement. The trouble is, students always come in pairs and only report the sum of their debts, and some people may report multiple times. This makes it very difficult for HZGD, and he suspects some might be misreporting. He wants to compile a debt list.

Input Format

The first line contains two positive integers $N$ and $M$, the number of students and the total number of times they report to HZGD. Each of the next $M$ lines contains three integers: the two students who report together and the sum of their reported debts.

Output Format

Output an $N$-line debt list. The $i$-th line corresponds to the debt amount of student $i$, with all amounts printed to two decimal places. If such a list cannot be produced, output IMPOSSIBLE. For inputs where a solution exists, it is guaranteed to be unique.

3 3
1 2 2
2 3 4
1 3 6

2.00
0.00
4.00

Hint

• For $30\%$ of the testdata, $1 \le N \le 10, 1 \le M \le 55$.
• For $60\%$ of the testdata, $1 \le N \le 100, 1 \le M \le 1000$.
• For $100\%$ of the testdata, $1 \le N \le 1000, 1 \le M \le 10^5$, and all input integers do not exceed $2 \times 10^6$.

Translated by ChatGPT 5