Sequence Reconstruction

Time limit3sMemory limit256 MB

Summary

Given M equations of the form a_i + a_j = k, reconstruct the integer sequence a_1..a_N or report ERROR when more than one solution exists.

Level: Hard8 of 10
Topics: Graph, Union-find, DFS, Math
Solved: No attempts yet

Problem

Wookje was playing with addition on a sequence of integers ${a_1,a_2,...,a_N}$ of length $N$ , but he lost the paper with the sequence written on it. Fortunately, the $M$ records he was playing with survive. Each record consists of three integers: the indices $i, j$ of two numbers and their sum $a_i+a_j$ . Using this information, you must reconstruct the original sequence.

Input

The first line gives the length $N$ of the sequence and the number $M$ of records.

Each of the next $M$ lines contains three integers $i,j,k$ separated by spaces. This means $a_i+a_j=k$ .

No input lacks a solution.

Output

Print the $N$ elements of the sequence Wookje was playing with, separated by spaces.

The elements of the sequence are guaranteed to be integers.

If more than one solution exists, print "ERROR" (without the quotes).

Constraints

$1 \leq N,M \leq 500,000$
$1 \leq i,j \leq N$
$-10^9 \leq k \leq 10^9$

Examples2

Example 1
Input
```
3 3
1 2 3
2 3 5
1 3 4
```
Expected output
```
1 2 3
```
Example 2
Input
```
4 4
1 2 3
2 3 5
3 4 7
4 1 5
```
Expected output
```
ERROR
```