무자비한 최단 경로

신촌 초급반 학생들은 그래프에서 최단 경로를 구하는 여러 방법을 공부했다. 학생들에게 벽을 느끼게 하고 싶었던 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$번째 줄에는 $1$번 마을에서 $i$번 마을까지 도착하는 최단 경로의 길이를 출력한다.