Debt Reconciliation

HZGD just led his N students to participate in the LXX^th NOI. After the contest, the students found that the reimbursement fees they were entitled to had still not been paid. As a result, they approached HZGD in pairs and reported only the sum of the debts for the two of them – and some students even report more than once. This has put HZGD in a difficult position as he is not sure whether some students are exaggerating their expenses. To resolve the matter, he decided to compile a debt list.

You are given a system of equations derived from the reports. Each report gives an equation of the form $$a_u + a_v = S,$$ where u and v are the indices of the two students reporting together and S is the total debt they claim. The students are numbered from 1 to N. Determine an assignment of individual debts \(a_1, a_2, \dots, a_N\) that satisfies all the given equations. If multiple solutions exist, output any one. If no valid assignment exists, output -1.

inputFormat

The first line contains two integers N and M, where N is the number of students and M is the number of reports.

Each of the following M lines contains three integers u, v, and S indicating that the sum of the debts of student u and student v is S (i.e. \(a_u + a_v = S\)). It is guaranteed that 1 ≤ u, v ≤ N and u ≠ v.

outputFormat

If there exists a valid assignment of debts \(a_1, a_2, \dots, a_N\) that satisfies all the reports, output N space-separated integers where the i-th integer represents the debt of student i. Otherwise, output -1.

sample

3 2
1 2 3
2 3 5

1 2 3