수열 복원

시간 제한3초메모리 제한256 MB

요약

a_i + a_j = k 형태의 M개 기록으로 정수 수열 a_1..a_N을 복원하고, 해가 여러 개면 ERROR를 출력한다.

난이도: 어려움10점 중 8점
유형: 그래프, 유니온 파인드, DFS, 수학
정답자: 아직 제출이 없습니다

문제

정수로 이루어진 길이 $N$ 짜리 수열 ${a_1,a_2,...,a_N}$ 과 덧셈으로 놀던 욱제는, 수열이 적혀있는 종이를 잃어버렸다. 다행히 가지고 놀던 $M$ 개의 기록은 남아있다. 각각의 기록은 세 정수로 이루어져 있으며, 그 의미는 두 수의 인덱스 $i, j$ 와 두 수의 합 $a_i+a_j$ 이다. 이 정보들을 토대로 원래의 수열이 무엇이었는지 복원하려고 한다.

입력

첫 번째 줄에 수열의 길이 $N$ 과 기록의 개수 $M$ 이 주어진다.

두 번째 줄부터 $M$ 개의 줄에 걸쳐 각각 세 정수 $i,j,k$ 가 공백으로 구분되어 주어진다. 이는 $a_i+a_j=k$ 임을 의미한다.

답이 존재하지 않는 입력은 없다.

출력

욱제가 가지고 놀던 수열의 원소 $N$ 개를 공백으로 구분하여 출력한다.

수열의 원소는 정수임이 보장된다.

답이 여러개 존재할 수 있다면 "ERROR"(따옴표 제외)를 출력한다.

제한

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

예제2

예제 1
입력
```
3 3
1 2 3
2 3 5
1 3 4
```
예상 출력
```
1 2 3
```
예제 2
입력
```
4 4
1 2 3
2 3 5
3 4 7
4 1 5
```
예상 출력
```
ERROR
```