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비트 정수 범위를 넘을 수 있으니 주의하시오.