#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("pitici.in");
ofstream cout("pitici.out");
using pii = pair<int,int>;
const int nmax = 1020 + 1;
int n , k , m , a , b , c ;
long long dp[nmax][nmax] , v[nmax] , ind;
bool viz[nmax];
struct edge{ int y , c;};
vector<edge>g[nmax];
vector<edge>t[nmax];
void tsort(int x)
{
    viz[x] = 1;
    for(auto it : g[x])
        if(!viz[it.y])
            tsort(it.y);
    v[ind--] = x;
}
struct elem{ int y , ind, c;};
struct cmp
{
    bool operator()(elem a , elem b)
    {
        return dp[a.y][a.ind]+a.c > dp[b.y][b.ind]+b.c;
    }
};
int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= m ; ++i)
    {
        cin >> a >> b >> c;
        g[a].push_back({b,c});
        t[b].push_back({a,c});
    }
    ind = n;
    tsort(1);
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= k ; ++j) dp[i][j] = -1;
    }
    dp[1][1] = 0;
    for(int i = 2 ; i <= n ; ++i)
    {
        priority_queue<elem,vector<elem>,cmp>pq;
        for(auto it : t[v[i]])
        {
            pq.push({it.y,1,it.c});
        }
        for(int cnt = 1 ; cnt <= k ; ++cnt)
        {
            if(pq.empty()) break;
            elem aux = pq.top();
            pq.pop();
            dp[v[i]][cnt] = dp[aux.y][aux.ind] + aux.c;
            if(dp[aux.y][aux.ind+1]==-1) continue;
            aux.ind++;
            pq.push(aux);
        }
    }
    for(int i = 1 ; i <= k ; ++i) cout << dp[n][i] << ' ';
    return 0;
}