#include<fstream>
#include<vector>
#include<queue>
#include<cassert>
using namespace std;
using pii = pair<int,int>;

ifstream cin("pitici.in");
ofstream cout("pitici.out");

constexpr int NMAX = 1020;
constexpr int oo = 2e9;

vector<pii> nexty[NMAX],from[NMAX];

int in[NMAX];

int main()
{
    int n,m,k,a,b,c; cin >> n >> m >> k;
    for(int i = 1; i <= m ; i++)
        {
            cin >> a >> b >> c; ++in[b];
            nexty[a].push_back({b,c});
            from[b].push_back({a,c});
        }

    vector<vector<int>> dp(n + 1,vector<int>(k+1,oo)); dp[1][1] = 0; queue<int> q;
    vector<bool> viz(n+1,false); viz[1] = 1; vector<int> info(n+1,1),cost(n+1,0);
    for(auto &it : nexty[1]) if((--in[it.first]) == 0) q.push(it.first);
    while(!q.empty())
        {
            int v = q.front(); q.pop(); assert(!viz[v]); viz[v] = 1;
            priority_queue<pii,vector<pii>,greater<pii>> pq;
            for(auto &it : from[v])
                {
                    assert(viz[it.first]); cost[it.first] = it.second;
                    pq.push({dp[it.first][1]+it.second,it.first});
                }

            for(int j = 1 ; j <= k ; j++)
                {
                    pii t = pq.top(); pq.pop(); dp[v][j] = t.first;
                    if(info[t.second] < k)
                        {
                            pq.push({dp[t.second][++info[t.second]]+
                            cost[t.second],t.second});
                        }
                }

            for(auto &it : from[v])
                info[it.first] = 1;
            for(auto &it : nexty[v])
                {
                    if((--in[it.first])==0)
                        q.push(it.first);
                }
        }

    for(int i = 1; i <= k ; i++)
        cout << dp[n][i] << " ";
}