수열 복원

$n$개의 양의 정수로 이루어진 수열 $a_0$, $a_1$, $\dots$, $a_{n-1}$이 적혀 있다. 수열의 값은 알려져 있지 않지만, 인덱스 $i$와 $j$를 사용한 $a_i + a_j$ 꼴의 합 $m$개가 주어진다. 이 합들로부터 수열 $a_0$, $a_1$, $\dots$, $a_{n-1}$을 구하는 recover 프로그램을 작성하라.

첫째 줄에 $n$, 둘째 줄에 $m$이 주어진다. 이어지는 $m$개의 줄에는 공백으로 구분된 정수 3개가 주어지며, 차례대로 i, j, $a_i + a_j$이다. 여기서 $i$와 $j$는 수열의 인덱스이고 $i < j$이다. 두 인덱스 모두 0 이상 $n - 1$ 이하이다.

수열의 원소를 인덱스 순서대로 한 줄에 출력하고, 원소 사이는 공백 한 칸으로 구분한다. 복원 방법이 여러 가지라면 그중 하나를 출력한다.

• $2 < n < 500$
• $2 < m < 2000$
• $n \le m$
• $n$과 $m$은 정수이다.
• 수열 $a_0$, $a_1$, $\dots$, $a_{n-1}$의 원소는 2000보다 작은 양의 정수이다.
• 입력은 이 수열을 복원할 수 있도록 주어진다.