# 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$.

Sample Input 1 | Sample Output 1 |
---|---|

4 2 1 2 3 3 4 2 |
0 3 0 2 |

Sample Input 2 | Sample Output 2 |
---|---|

8 1 2 7 0 |
0 0 0 0 0 0 0 0 |

Sample Input 3 | Sample Output 3 |
---|---|

8 1 3 3 7 |
-1 |

Sample Input 4 | Sample Output 4 |
---|---|

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 |