#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

const int max_size = 1020, INF = 1e9 + 1;

struct strheap{
    int x, c, nrord;
    bool operator < (const strheap &aux) const
    {
        return c > aux.c;
    }
};

int viz[max_size], costuri[max_size][max_size];
vector <int> mc[max_size], invmc[max_size], topsort, sol[max_size];
priority_queue <strheap> heap;

void dfs (int nod)
{
    viz[nod] = 1;
    for (auto f : mc[nod])
    {
        if (!viz[f])
        {
            dfs(f);
        }
    }
    topsort.push_back(nod);
}

int main ()
{
    int n, m, k;
    in >> n >> m >> k;
    while (m--)
    {
        int x, y, z;
        in >> x >> y >> z;
        costuri[x][y] = z;
        mc[x].push_back(y);
        invmc[y].push_back(x);
    }
    dfs(1);
    reverse(topsort.begin(), topsort.end());
    sol[1].push_back(0);
    for (auto f : topsort)
    {
        while (!heap.empty())
        {
            heap.pop();
        }
        for (auto ff : invmc[f])
        {
            heap.push({ff, sol[ff][0] + costuri[ff][f], 0});
        }
        int kk = k;
        //out << f << " ";
        while (!heap.empty() && kk--)
        {
            strheap aux = heap.top();
            heap.pop();
          //  out << aux.c << " ";
            sol[f].push_back(aux.c);
            if (aux.nrord + 1 < sol[aux.x].size())
            {
                heap.push({aux.x, sol[aux.x][aux.nrord + 1] + costuri[aux.x][f], aux.nrord + 1});
            }
        }
        //out << '\n';
    }
    for (auto f : sol[n])
    {
        out << f << " ";
    }
    in.close();
    out.close();
    return 0;
}