#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long int
int n, m, k;
vector<vector<pair<int,int>>> g;
vector<vector<int>> dist;
const int INF = 9e15;
void dij()
{
priority_queue <
pair<int,int>,
vector<pair<int,int>>,
greater<pair<int,int>>
> pq;
pq.push({0,1});
while(!pq.empty())
{
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
if(dist[u][k-1] < d) continue;
for(auto e: g[u])
{
int v = e.first;
int c = e.second;
if(dist[v][k-1] > c+d)
{
dist[v][k-1] = c+d;
pq.push({dist[v][k-1], v});
sort(dist[v].begin(), dist[v].end());
}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
g.resize(n+1);
dist.resize(n+1);
for(int i = 1; i <= n; i++)
{
dist[i].resize(k);
for(int j = 0; j <k; ++j)
{
dist[i][j] = INF;
}
}
dist[1][0] = 0;
for(int i = 0; i < m; ++i)
{
int u, v, c;
cin >> u >> v >> c;
g[u].push_back({v,c});
}
dij();
for(int i = 0; i < k; ++i)
{
cout << dist[n][i] << " ";
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAiXG4iCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZyBpbnQKIAppbnQgbiwgbSwgazsKdmVjdG9yPHZlY3RvcjxwYWlyPGludCxpbnQ+Pj4gZzsKdmVjdG9yPHZlY3RvcjxpbnQ+PiBkaXN0OyAKY29uc3QgaW50IElORiA9IDllMTU7CiAKdm9pZCBkaWooKQp7CgkKCXByaW9yaXR5X3F1ZXVlIDwKCSAgcGFpcjxpbnQsaW50PiwgCgkgIHZlY3RvcjxwYWlyPGludCxpbnQ+PiwgCgkgIGdyZWF0ZXI8cGFpcjxpbnQsaW50Pj4KCT4gcHE7IAogCglwcS5wdXNoKHswLDF9KTsKIAoJd2hpbGUoIXBxLmVtcHR5KCkpCgl7CgkJaW50IHUgPSBwcS50b3AoKS5zZWNvbmQ7CgkJaW50IGQgPSBwcS50b3AoKS5maXJzdDsKCQlwcS5wb3AoKTsKCQkKCQlpZihkaXN0W3VdW2stMV0gPCBkKSBjb250aW51ZTsKIAoJCWZvcihhdXRvIGU6IGdbdV0pCgkJewoJCQlpbnQgdiA9IGUuZmlyc3Q7CgkJCWludCBjID0gZS5zZWNvbmQ7CiAKCQkJaWYoZGlzdFt2XVtrLTFdID4gYytkKSAKCQkJewoJCQkJZGlzdFt2XVtrLTFdID0gYytkOwoJCQkJcHEucHVzaCh7ZGlzdFt2XVtrLTFdLCB2fSk7CgkJCQlzb3J0KGRpc3Rbdl0uYmVnaW4oKSwgZGlzdFt2XS5lbmQoKSk7CgkJCX0KCQl9Cgl9Cn0KIAppbnQzMl90IG1haW4oKQp7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoTlVMTCk7CgljaW4gPj4gbiA+PiBtID4+IGs7CglnLnJlc2l6ZShuKzEpOwoJZGlzdC5yZXNpemUobisxKTsKCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQoJewoJCWRpc3RbaV0ucmVzaXplKGspOwoJCWZvcihpbnQgaiA9IDA7IGogPGs7ICsraikKCQl7CgkJCWRpc3RbaV1bal0gPSBJTkY7CgkJfQoJfQoJZGlzdFsxXVswXSA9IDA7Cglmb3IoaW50IGkgPSAwOyBpIDwgbTsgKytpKQoJewoJCWludCB1LCB2LCBjOwoJCWNpbiA+PiB1ID4+IHYgPj4gYzsKCQlnW3VdLnB1c2hfYmFjayh7dixjfSk7Cgl9CgkKCWRpaigpOwogCglmb3IoaW50IGkgPSAwOyBpIDwgazsgKytpKQoJewoJCWNvdXQgPDwgZGlzdFtuXVtpXSA8PCAiICI7Cgl9Cn0=