#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>

#define MAXN 1024

using namespace std;

int matPaths[MAXN][MAXN];
short used[MAXN];
short dist[MAXN];
bitset<MAXN> bitsetVisited;

struct Edge
{
    Edge() :
        DestNode(0),
        Cost(0)
    {}
    
    Edge(short destNode, short cost) :
        DestNode(destNode),
        Cost(cost)
    {}

    short DestNode;
    short Cost;
};

static ostream& operator << (ostream& os, const Edge& e)
{
    os << "(" << e.DestNode << " " << e.Cost << ")";
    return os;
}

struct Entry
{
    Entry() :
        NodeList(0),
        Cost(0)
    {}

    Entry(short nodeList, int cost) :
        NodeList(nodeList),
        Cost(cost)
    {}

    int Cost;
    short NodeList;
    
    bool operator < (const Entry& rhs) const
    {
        return Cost > rhs.Cost;
    }
};

static void EnqueueNeighbors(const vector<Edge>& nodeNeighbors, bitset<MAXN>& bitsetVisited, queue<short>& Q)
{
    for (vector<Edge>::const_iterator it=nodeNeighbors.begin(); it!=nodeNeighbors.end(); ++it)
    {
        if (bitsetVisited[it->DestNode] == false)
        {
            bitsetVisited[it->DestNode] = true;
            Q.push(it->DestNode);
        }
    }
}

vector<Edge> graphForwardEdges[MAXN];
vector<Edge> graphBackwardEdges[MAXN];

int main()
{
    int n, m, k;
    fstream fin("pitici.in", fstream::in);
    fstream fout("pitici.out", fstream::out);
    
    fin >> n >> m >> k;
    //cout << n << " " << m << " " << k << endl;
    
    for (int i=0; i<m; ++i)
    {
        short x, y, c;
        fin >> x >> y >> c;
        
        graphForwardEdges[x].push_back(Edge(y, c));
        graphBackwardEdges[y].push_back(Edge(x, c));
    }
    
    /*ostream_iterator<Edge> itOutEdge(cout, " ");
    for (int i=1; i<=n; ++i)
    {
        cout << i << " -> ";
        copy(graphForwardEdges[i].begin(), graphForwardEdges[i].end(), itOutEdge);
        cout << endl;
    }*/
    
    queue<short> Q;
    bitsetVisited[1] = true;
    EnqueueNeighbors(graphForwardEdges[1], bitsetVisited, Q);
    
    while (!Q.empty())
    {
        const int currentNode = Q.front();
        Q.pop();
        
        EnqueueNeighbors(graphForwardEdges[currentNode], bitsetVisited, Q);
        
        ::fill(used, used+n, 0);
        
        priority_queue<Entry> pqPathCosts;
        
        for (vector<Edge>::iterator it=graphBackwardEdges[currentNode].begin(); it!=graphBackwardEdges[currentNode].end(); ++it)
        {
            used[it->DestNode] = 1;
            dist[it->DestNode] = it->Cost;
            pqPathCosts.push(Entry(it->DestNode, matPaths[it->DestNode][1] + it->Cost));
        }
        
        // perform n-way merge sort
        while (pqPathCosts.empty() == false && matPaths[currentNode][0] <= k)
        {
            const Entry entry = pqPathCosts.top();
            pqPathCosts.pop();
            matPaths[currentNode][++matPaths[currentNode][0]] = entry.Cost;
            
            if (used[entry.NodeList] < matPaths[entry.NodeList][0])
            {
                ++used[entry.NodeList];
                pqPathCosts.push(Entry(entry.NodeList, matPaths[entry.NodeList][used[entry.NodeList]] + dist[entry.NodeList]));
            }
        }
    }
    
    ostream_iterator<int> itOut(fout, " ");
    copy(&matPaths[n][1], &matPaths[n][1] + k, itOut);
    fout << endl;
    
    return 0;
}