页面无法加载？点击这里可能会修复。
Placeholder

#2309

[중등부] 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
需要登录才能编写代码。