#include <bits/stdc++.h>

using namespace std;

vector <int> v[1050];

vector <int> l[1050];

vector <int> ll[1050];

vector <int> vv[1050];

deque <int> q;

int in[1050];

int s[1050];

int dp[1050];

int cc[1050];

int sp[1050];

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;

int main()
{
    ifstream cin("pitici.in");
    ofstream cout("pitici.out");
    int n,m,k,x,y,z;
    cin>>n>>m>>k;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        v[x].push_back(y);
        vv[y].push_back(x);
        ll[y].push_back(z);
        l[x].push_back(z);
        in[y]++;
    }
    int nn=0;
    for(int i=1;i<=n;++i)
    {
        if(in[i]==0)
        {
            q.push_back(i);
        }
    }
    while(q.size())
    {
        ++nn;
        s[nn]=q.front();
        for(auto a:v[q.front()])
        {
            --in[a];
            if(in[a]==0)
            {
                q.push_back(a);
            }
        }
        q.pop_front();
    }
    for(int i=1;i<=nn;++i)
    {
        dp[s[i]]=INT_MAX;
        if(s[i]==1)
        {
            dp[s[i]]=0;
            cc[s[i]]=1;
        }
        else
        {
            for(int h=0;h<vv[s[i]].size();++h)
            {
                int nd=vv[s[i]][h],ln=ll[s[i]][h];
                if(dp[nd]!=INT_MAX)
                {
                    if(dp[nd]+ln<dp[s[i]])
                    {
                        dp[s[i]]=dp[nd]+ln;
                        cc[s[i]]=0;
                    }
                    if(dp[nd]+ln==dp[s[i]])
                    {
                        cc[s[i]]+=cc[nd];
                    }
                }
            }
        }
    }
    pq.push({dp[n],{n,1}});
    int ix=1;
    while(pq.size())
    {
        int nd,ln,da;
        nd=pq.top().second.first;
        ln=pq.top().first;
        da=pq.top().second.second;
        pq.pop();
        if(da==1)
        {


        if(k<=cc[nd])
        {
            sp[ix]+=ln;
            break;
        }
        else
        {
            sp[ix]+=ln;
            sp[ix+cc[nd]]-=ln;
            ix+=cc[nd];
        }
        }
            for(int h=0;h<vv[nd].size();++h)
            {
                int nod=vv[nd][h],lng=ll[nd][h];
                        int dif=dp[nod]+lng-dp[nd];
                        if(dif==0)
                        {


                        pq.push({ln+dif,{nod,0}});
                        }
                        else
                        {
                            pq.push({ln+dif,{nod,1}});
                        }

            }
    }
    for(int i=1;i<=k;++i)
    {
        sp[i]=sp[i-1]+sp[i];
        cout<<sp[i]<<" ";
    }
    return 0;
}