Difference Constraints System

Problem Description

Given a system of $m$ inequalities with $n$ unknowns of the form:

$$\begin{cases} x_{c_1} - x_{c'_1} \le y_1 \\ x_{c_2} - x_{c'_2} \le y_2 \\ \cdots \\ x_{c_m} - x_{c'_m} \le y_m \end{cases}$$

Find a non-negative solution satisfying this system of inequalities, with each variable as small as possible.

Input Format

The first line contains two positive integers $n, m$, the number of unknowns and the number of inequalities.

The next $m$ lines each contain three integers $c, c', y$, representing an inequality $x_c - x_{c'} \le y$.

It is guaranteed that $1 \le n, m \le 5 \times 10^3,\ -10^4 \le y \le 10^4,\ 1 \le c, c' \le n,\ c \ne c'$.

Output Format

One line with $n$ numbers: $x_1, x_2, \dots, x_n$. If there is no solution, output -1.

Sample Input

3 3
1 2 3
2 3 -2
1 3 1

Sample Output

0 0 2