저울추 질량 정하기

질량을 모르는 저울추가 N개 있고, 각 저울추에는 1번부터 N번까지 번호가 붙어 있다. 질량을 모르면 저울추를 사용할 수 없으므로, 모든 저울추에 질량을 정해 주려고 한다.

정확한 질량은 잴 수 없지만, 크기를 보고 대략적인 비교는 할 수 있다. 예를 들어 a번 추가 b번 추보다 훨씬 커 보이면, a번 추의 질량이 b번 추의 질량보다 크다고 판단할 수 있다. 더 일반적으로, 각 비교 정보는 다음 두 형태 중 하나이다. 여기서 a와 b는 1 이상 N 이하의 서로 다른 번호이고, x는 음수일 수도 있는 정수이다.

• mass[a] <= mass[b] + x
• mass[a] >= mass[b] + x

이러한 비교 정보가 M개 주어질 때, 모든 비교를 만족하도록 각 저울추의 질량을 정하시오.

첫째 줄에 저울추의 개수 N과 비교 정보의 개수 M이 주어진다 (1 <= N <= 1,000, 1 <= M <= 10,000).

다음 M개의 줄에는 비교 정보가 a t b x 형식으로 주어진다. a와 b는 1 이상 N 이하의 서로 다른 저울추 번호이고, x는 |x| <= 10,000인 정수이다.

t가 0이면 mass[a] <= mass[b] + x를 뜻하고, t가 1이면 mass[a] >= mass[b] + x를 뜻한다.

N개의 줄에 걸쳐 질량을 출력한다. i번째 줄에는 i번 저울추의 질량을 출력한다. 각 질량은 1,000,000 이하의 자연수여야 한다.

모든 비교를 만족하는 질량 배정이 불가능하면 첫째 줄에 -1만 출력한다. 가능한 배정이 여러 개라면 그중 아무거나 하나를 출력해도 된다.