At the running contest, jury used a new computerized stopwatch system to ensure the most
accurate measuring of results. Unfortunately, despite very successfull trials,
the system malfunctioned during the actual contest.

Jury was so confident in the new system that it did not use the old mechanical stopwatches.
So the only way to determine outcome was to compare visual impressions of the people watching the contest.
M such impressions were recorded, each in one of two forms:
"runner A finished before runner B" and "runners A and B finished at the same time".

You task is to assign a place p_{i} to each of N runners,
such that

If there is a record that A and B finished at the same time,
then p_{A} = p_{B}.

If there is a record that A finished before B,
then p_{A} < p_{B}.

Additionally, places must be allocated as densely as possible, i.e.
1 ≤ p_{i} ≤ K for minimum possible value of K.

Input file format

Input file contains integers N M followed by M
pairs A_{i} B_{i} c_{i},
where
c_{i} = 0 means the record "runners A_{i} and B_{i} finished at the same time",
c_{i} = 1 means the record "runner A_{i} finished before B_{i}".

Output file format

Output file must contain either a single number −1, if the places could not be assigned,
or a sequence of N numbers p_{i}.
If several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 10000,
0 ≤ M ≤ 10^{6},
1 ≤ A_{i}, B_{i} ≤ N