Choosing Weight Masses

There are N weights whose masses are unknown, numbered from 1 to N. Because a weight with an unknown mass is not useful, we want to assign a mass to every weight.

Exact measurement is impossible, but rough size comparisons are available. For example, if weight a looks much larger than weight b, we may know that the mass of a is greater than the mass of b. More generally, each comparison is one of the following forms, where a and b are different numbers between 1 and N, and x is an integer that may be negative.

• mass[a] <= mass[b] + x
• mass[a] >= mass[b] + x

Given M such comparisons, assign masses to all weights so that every comparison is satisfied.

The first line contains the number of weights N and the number of comparisons M (1 <= N <= 1,000, 1 <= M <= 10,000).

Each of the next M lines contains a t b x. The numbers a and b are distinct weight numbers between 1 and N, and x is an integer with |x| <= 10,000.

If t is 0, the comparison means mass[a] <= mass[b] + x. If t is 1, it means mass[a] >= mass[b] + x.

Print N lines. On the i-th line, print the mass assigned to weight i. Each mass must be a positive integer not greater than 1,000,000.

If no assignment satisfies all comparisons, print only -1. If several assignments are possible, print any one of them.