34901번 - 자재 옮기기

문제

좌표평면 위에 창고가 $N$개 있으며 $i$번째 창고의 위치는 $(x_i, y_i)$이다. 각 창고에는 자재가 하나씩 있으며 이루매는 모든 자재를 한 창고에 모으려고 한다.

이루매는 $i$번째 창고에 있는 자재를 $j$번째 창고로 옮길 수 있으며 이 때 드는 힘은 $|x_i - x_j| + |y_i - y_j| + c_j$이다. 단, 한번에 옮길 수 있는 자재의 개수에 제한은 없으며 창고가 아닌 곳에 자재를 내려놓을 수는 없다.

1ドル \leq k \leq N$인 모든 $k$에 대해 모든 자재를 $k$번째 창고로 옮길 때 드는 최소 힘을 구해보자.

입력

첫째 줄에 창고의 개수를 나타내는 정수 $N$이 주어진다. $(2 \leq N \leq 2000)$

다음 $N$줄에 걸쳐 $i+1$줄에 $i$번째 창고에 대한 정보를 나타내는 세 정수 $x_i, y_i, c_i$가 공백으로 구분되어 주어진다. 모든 창고의 위치가 다름이 보장된다. $(1\leq x_i, y_i, c_i \leq 10^9)$

출력

$N$개의 정수를 공백으로 구분해 출력한다. 이 때 $i$번째 수는 모든 자재를 $i$번째 창고로 옮길 때 드는 최소 힘을 나타낸다.

제한

노트