페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2310

[고등부] 2024 KOI 2차대회 대비 모의고사 (3주차)

수열 복원
스페셜 저지
서브태스크
2초 1024MB

문제

수열 a는 n개의 양의 정수 a_0, a_1, \dots, a_{n-1}의 시퀀스다.

이 수열의 숫자들은 주어지지 않지만, a_i + a_j 값이 m개 주어진다. 여기서 i와 j는 수열의 인덱스다.

주어진 합들을 토대로, a_0, a_1, \dots, a_{n-1}의 값을 찾는 프로그램을 작성하시오.


입력

첫 번째와 두 번째 줄에 각각 n과 m의 값이 주어진다.

그 다음 m개의 줄에 공백으로 구분된 3개의 정수가 주어진다: i, j, a_i + a_j.

여기서 i와 j는 수열의 인덱스이며, 인덱스 i와 j의 값은 0과 n-1 사이다.

  • 2 ≤ n < 500

  • 2 ≤ m < 2, 000

  • n ≤ m

  • n과 m은 정수다.

a_0, a_1, \dots, a_{n-1}은 양의 정수이며, 2, 000보다 작다.

입력 데이터는 주어진 수열을 복원할 수 있도록 보장된다.


출력

첫 줄에 수열의 숫자를 출력해야 한다.

이 숫자들은 인덱스 순으로 정렬되어야 하며 각각의 숫자 사이에는 정확히 한 개의 공백이 있어야 한다.

수열의 복원이 여러 가지 방법으로 이루어질 수 있는 경우, 그 중 하나를 출력한다.


부분문제

번호 점수 조건
#110점

n \le 3

#210점

m \le 3

#330점

n \le 15, a_0, a_1, \dots, a_{n-1}을 1 이상 3 이하의 정수로 만들 수 있는 입력 데이터만 주어진다.

#450점

추가 제한 없음


예제 

4
5
0 1 5
1 2 6
0 2 7
1 3 8
2 3 10
3 2 4 6
로그인해야 코드를 작성할 수 있어요.