Problem G
Array Constraints

There is a hidden array $a$ of $n$ non-negative integers. You are given $k$ constraints on this array, of the form $a_ i + a_ j = x$. Recover the lexicographically smallest possible array $a$, or determine that no such array exists.

An array $s$ of size $n$ is lexicographically smaller than an array $t$ of size $n$ if $s \ne t$ and in the first position $i$ where $s$ and $t$ differ, $s_ i$ is less than $t_ i$. For example, $s=[2, 3, 1, 8]$ is lexicographically smaller than $t=[2, 3, 4, 2]$, because they first differ at position $3$, and $s_3 = 1$ is less than $t_3 = 4$.

Input

The first line of the input contains two integers $n$ and $k$ ($1\le n, k\le 2\cdot 10^5$) —the size of the array and the number of constraints, respectively.

Each of the next $k$ lines contains three integers $i$, $j$, and $x$ ($1\le i, j \le n$, $0\le x\le 10^9$), representing the constraint $a_ i+a_ j=x$.

Output

If there is no valid array $a$, print a single integer $-1$. Otherwise, print a line containing $n$ non-negative integers —the lexicographically smallest possible $a$.

4 2
1 2 3
3 4 2

0 3 0 2

8 1
2 7 0

0 0 0 0 0 0 0 0

8 1
3 3 7

-1

15 14
1 6 6
12 8 1
4 9 5
10 8 3
6 15 5
13 13 4
6 1 6
11 9 9
7 10 9
1 5 4
1 6 6
11 4 12
7 12 7
2 11 14

1 6 0 4 3 5 6 0 1 3 8 1 2 0 0