DevNight 운영

GIST에서는 2022년부터 매년 가을 'GIST DevNight' (개발자의 밤, Developers' Night) 행사가 열린다. DevNight 행사를 통해 개발자들끼리 정보를 공유하고 친목을 도모할 수 있다. 행사는 컨퍼런스 룸에서 열리는 컨퍼런스와 커뮤니케이션 룸에서 열리는 친목 활동으로 나누어져 있다.

2024년도 GIST DevNight는 정점 $N$개와 길이가 있는 양방향 간선 $M$개로 구성된 건물에서 열린다. 각각의 정점에는 컨퍼런스 룸 또는 커뮤니케이션 룸 둘 중 하나가 자리잡고 있다. 커뮤니케이션 룸의 수는 $K$개이며, $1$번 정점부터 $K$번 정점까지는 커뮤니케이션 룸이고 $K+1$번 정점부터 $N$번 정점까지는 컨퍼런스 룸이다.

컨퍼런스 하나가 끝나면 개발자들은 커뮤니케이션 룸으로 이동한다. 이때 자신의 위치에 따라 각 커뮤니케이션 룸에 대한 선호도가 달라진다. 모든 사람은 컨퍼런스 룸의 위치로부터 최단 경로의 길이가 짧은 커뮤니케이션 룸을 더 선호하며, 만약 그런 커뮤니케이션 룸이 $2$개 이상 있으면 정점의 번호가 작은 커뮤니케이션 룸을 더 선호한다.

2023년도 DevNight 때는 개발자들이 가장 선호도가 높은 커뮤니케이션 룸을 이용했다. 그러나 그러다 보니 방 하나에만 지나치게 사람이 많이 모이는 일이 발생하여, 2024년도 DevNight에서는 모든 사람이 두 번째로 선호도가 높은 커뮤니케이션 룸을 이용하도록 정책이 바뀌었다. DevNight 운영자인 당신은 각각의 컨퍼런스 룸에 대하여 그 방에서 컨퍼런스가 끝나면 개발자들은 커뮤니케이션 룸으로 가기 위해 얼마나 걸어가야 하는지 궁금해졌다. 보성이를 도와주는 프로그램을 만들어 보자.

첫째 줄에 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($3 \leq N \leq 100\,000, 2 \leq M \leq 300\,000, 2 \leq K < N$)

둘째 줄부터 $M$줄에 걸쳐 간선의 정보를 나타내는 세 정수 $s, e, d$가 주어진다. ($1 \leq s, e \leq N, s \neq e, 1 \leq d \leq 10^6$) 이는 두 정점 $s$와 $e$를 잇는 길이 $d$의 간선이 존재함을 의미한다.

임의의 두 정점 사이를 잇는 간선은 최대 $1$개이다. 또 주어진 그래프는 반드시 연결 그래프이다.

$K+1$ 이상 $N$ 이하의 모든 자연수 $x$에 대하여 $x$번 정점에 있는 사람이 두 번째로 선호도가 높은 커뮤니케이션 룸까지 가기 위한 최단 경로의 길이를 순서대로 공백으로 구분하여 출력한다. 정답이 32비트 정수 범위를 넘을 수 있음에 주의하시오.