25500번 - 무자비한 최단 경로

문제

신촌 초급반 학생들은 그래프에서 최단 경로를 구하는 여러 방법들을 공부했다. 그들에게 벽을 느끼게 하고 싶었던 djs100201은 무자비한 최단 경로 문제를 만들었다.

1ドル$번 부터 $N$번까지 번호가 매겨진 총 $N$개의 마을이 있다. $i$번째 마을의 위치는 $(x_i,y_i,z_i)$로 표현된다. 1ドル$이상 $N$이하의 서로 다른 두 정수 $i,j$에 대해, $i$번 마을과 $j$번 마을을 잇는 $\min(|x_i-x_j|,|y_i-y_j|)$만큼의 길이를 가진 양방향 도로가 존재한다. 또한 만약 $z_i+z_j$가 $K$로 나누어 떨어진다면, $i$번 마을과 $j$번 마을을 잇는 $z_i+z_j$의 길이를 가진 양방향 도로 또한 존재한다.

이때 1ドル$번 마을에서 각 마을로 도착하는 최단 경로의 길이를 모두 구해보자.

입력

첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \leq N,K \leq 200,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i+1$번째 줄에는 $i$번 마을의 위치를 나타내는 세 정수 $(x_i,y_i,z_i)$가 공백으로 구분되어 주어진다. $(0 \leq x_i,y_i,z_i \leq 10^9)$

출력

총 $N$줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번 마을에 도착하는 최단 경로의 길이를 출력한다.

제한

힌트