DevNight Operations

GIST has held the GIST DevNight (Developers' Night) event every autumn since 2022. At DevNight, developers share information and build friendships. The event is split into a conference held in conference rooms and social activities held in communication rooms.

The 2024 GIST DevNight takes place in a building with $N$ vertices and $M$ bidirectional edges, each with a length. Each vertex holds either a conference room or a communication room. There are $K$ communication rooms: vertices 1 through $K$ are communication rooms, and vertices $K+1$ through $N$ are conference rooms.

When a conference ends, developers move to a communication room. Each person's preference for the communication rooms depends on where they are. Everyone prefers the communication room with the shorter shortest path from their conference room. If two or more communication rooms tie, they prefer the one with the smaller vertex number.

In 2023, developers all used their most preferred communication room. Too many people crowded into a single room, so in 2024 the policy changed: everyone uses their second-most preferred communication room. As the DevNight operator, you want to know how far developers must walk to reach a communication room after a conference in each conference room. Write a program to help Bosung.

The first line contains integers $N$, $M$, and $K$, separated by spaces. ($3 \leq N \leq 100\,000$, $2 \leq M \leq 300\,000$, $2 \leq K < N$)

The next $M$ lines each contain three integers $s$, $e$, and $d$. ($1 \leq s, e \leq N$, $s \neq e$, $1 \leq d \leq 10^6$) This means there is an edge of length $d$ connecting vertices $s$ and $e$.

There is at most one edge between any two vertices. The given graph is always connected.

For every integer $x$ from $K+1$ to $N$, in order, print the length of the shortest path from vertex $x$ to its second-most preferred communication room, separated by spaces. The answer can exceed the 32-bit integer range, so be careful.