어느 연구소에서 서로 다른 \(N\)개의 차원을 관측하고 있다. 각 차원에는 고유한 기준 시각 \(x_i\) (\(1 \le i \le N\))가 존재한다.

연구소는 차원 간의 포탈을 통해 차원 간의 상대적인 시차를 측정하는 \(M\)개의 연구 보고서를 수집했다. 각 보고서는 다음과 같은 형태이다.

• "\(A\)번 차원의 시각 \(x_A\)와 \(B\)번 차원의 시각 \(x_B\)를 비교했을 때, \(B\)번 차원의 시각은 \(A\)번 차원의 시각보다 최대 \(C\)초만큼 클 수 있다."

연구팀은 보고서에 적힌 시차 제약 조건들을 모두 만족하도록 각 차원의 기준 시각 \(x_1, x_2, \dots, x_N\)을 정하고자 한다.

하지만 데이터 오류나 시공간 왜곡으로 인해 보고서들의 내용이 서로 모순되어 이를 만족하는 시각을 정할 수 없을 수도 있다.

모든 차원의 기준 시각은 \(0\) 이하의 정수이며, 가능한 시각 중 각 차원의 시각 \(x_i\)가 가질 수 있는 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 차원의 개수 \(N\)과 보고서의 개수 \(M\)이 공백으로 구분되어 주어진다. (\(2 \le N \le 1,000\), \(1 \le M \le 5,000\))

둘째 줄부터 \(M\)개의 줄에 걸쳐 각 보고서의 정보 \(A\), \(B\), \(C\)가 공백으로 구분되어 주어진다.

이는 \(x_B - x_A \le C\)라는 제약 조건을 의미한다. (\(1 \le A, B \le N\), \(A \ne B\), \(-10,000 \le C \le 10,000\))

출력

주어진 \(M\)개의 보고서 조건을 모두 만족하면서 \(x_i \le 0\)을 만족하는 해가 존재하지 않는다면 첫째 줄에 -1을 출력한다.

해가 존재하는 경우, 첫째 줄에 1번 차원부터 \(N\)번 차원까지의 기준 시각 \(x_1, x_2, \dots, x_N\)을 공백으로 구분하여 출력한다.

(만족하는 해 중 각 \(x_i\)가 가질 수 있는 최댓값을 출력한다.)

예제 입력 1

4 5
1 2 4
2 3 -2
3 1 1
1 4 5
4 3 -3

예제 출력 1

-3 1 -1 2

예제 입력 2

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

예제 출력 2

-1