#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
//cout<<1;
vector<vector<pair<int, int>>> adj(n + 1);
for(int i=0;i<m;i++){
int u, v, w;
cin>>u>>v>>w;
adj[u-1].push_back({v-1, w});
adj[v-1].push_back({u-1, w});
}
vector<vector<int>> dp(n + 1, vector<int>(k + 2, INT_MAX));
for(int i = 0;i <=k;i++){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
dp[0][i] = 0;
while(!pq.empty()){
auto tp = pq.top();
pq.pop();
int u = tp.second;
for(auto it : adj[u]){
int v = it.first;
int w = it.second;
if(i > 0){
if(dp[v][i] > min(dp[u][i-1] , dp[u][i] + w)){
dp[v][i] = min(dp[u][i-1] , dp[u][i] + w);
pq.push({dp[v][i], v});
}
}
else{
if(dp[v][i] > dp[u][i] + w){
dp[v][i] = dp[u][i] + w;
pq.push({dp[v][i], v});
}
}
}
}
}
for(int i = 0;i < n;i++){
cout<<dp[i][k]<<" ";
}
cout<<endl;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCl7CglpbnQgbixtLGs7CgljaW4+Pm4+Pm0+Pms7Ci8vY291dDw8MTsKCXZlY3Rvcjx2ZWN0b3I8cGFpcjxpbnQsIGludD4+PiBhZGoobiArIDEpOwoJCglmb3IoaW50IGk9MDtpPG07aSsrKXsKCQlpbnQgdSwgdiwgdzsKCQljaW4+PnU+PnY+Pnc7CgkJYWRqW3UtMV0ucHVzaF9iYWNrKHt2LTEsIHd9KTsKCQlhZGpbdi0xXS5wdXNoX2JhY2soe3UtMSwgd30pOwoJfQoJCgl2ZWN0b3I8dmVjdG9yPGludD4+IGRwKG4gKyAxLCB2ZWN0b3I8aW50PihrICsgMiwgSU5UX01BWCkpOwoJZm9yKGludCBpID0gMDtpIDw9aztpKyspewoJCXByaW9yaXR5X3F1ZXVlPHBhaXI8aW50LCBpbnQ+LCB2ZWN0b3I8cGFpcjxpbnQsIGludD4+LCBncmVhdGVyPHBhaXI8aW50LCBpbnQ+Pj4gcHE7CgkJcHEucHVzaCh7MCwgMH0pOwoJCWRwWzBdW2ldID0gMDsKCQl3aGlsZSghcHEuZW1wdHkoKSl7CgkJCWF1dG8gdHAgPSBwcS50b3AoKTsKCQkJcHEucG9wKCk7CgkJCWludCB1ID0gdHAuc2Vjb25kOwoJCQlmb3IoYXV0byBpdCA6IGFkalt1XSl7CgkJCQlpbnQgdiA9IGl0LmZpcnN0OwoJCQkJaW50IHcgPSBpdC5zZWNvbmQ7CgkJCQlpZihpID4gMCl7CgkJCQkJaWYoZHBbdl1baV0gPiBtaW4oZHBbdV1baS0xXSAsIGRwW3VdW2ldICsgdykpewoJCQkJCQlkcFt2XVtpXSA9IG1pbihkcFt1XVtpLTFdICwgZHBbdV1baV0gKyB3KTsKCQkJCQkJcHEucHVzaCh7ZHBbdl1baV0sIHZ9KTsKCQkJCQl9CgkJCQl9CgkJCQllbHNlewoJCQkJCWlmKGRwW3ZdW2ldID4gZHBbdV1baV0gKyB3KXsKCQkJCQkJZHBbdl1baV0gPSBkcFt1XVtpXSArIHc7CgkJCQkJCXBxLnB1c2goe2RwW3ZdW2ldLCB2fSk7CgkJCQkJfQoJCQkJfQoJCQl9CgoJCX0KCQkKCgl9Cglmb3IoaW50IGkgPSAwO2kgPCBuO2krKyl7CgkJY291dDw8ZHBbaV1ba108PCIgIjsKCX0KCWNvdXQ8PGVuZGw7Cgp9