#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

class cmp1 { public : bool operator () (const int &a, const int &b) { return a < b; } };
class cmp2 { public : bool operator () (const int &a, const int &b) { return a > b; } };
int n, m, k, l, PO[1024];
bool F[1024];
vector < pair < int, int > > G[1024];
multiset < int, cmp1 > HMin[1024];
multiset < int, cmp2 > HMax[1024];

void DFS(int node)
{
    F[node] = true;
    for (vector < pair < int, int > > :: iterator it = G[node].begin(); it != G[node].end(); it ++)
    {
        if (!F[it->first])
        {
            DFS(it->first);
        }
    }
    PO[++PO[0]] = node;
}

int main()
{
    fin >> n >> m >> k;
    for (int a, b, c, i = 1; i <= m; i ++)
    {
        fin >> a >> b >> c;
        G[a].push_back( { b, c } );
    }
    DFS(1);
    HMin[1].insert(0);
    HMax[1].insert(0);
    for (int i = n; i >= 1; i --)
    {
        if (PO[i] == n) continue;
        while (!HMin[PO[i]].empty())
        {
            int dmin = *HMin[PO[i]].begin();
            HMin[PO[i]].erase(HMin[PO[i]].begin());

            for (vector < pair < int, int > > :: iterator it = G[PO[i]].begin(); it != G[PO[i]].end(); it ++)
            {
                if (HMin[it->first].size() < k)
                {
                    HMin[it->first].insert(dmin + it->second);
                    HMax[it->first].insert(dmin + it->second);
                }
                else if (dmin + it->second < *HMax[it->first].begin())
                {
                    HMin[it->first].insert(dmin + it->second);
                    HMin[it->first].erase(HMin[it->first].find(*HMax[it->first].begin()));
                    HMax[it->first].insert(dmin + it->second);
                    HMax[it->first].erase(HMax[it->first].begin());
                }
            }
        }
    }

    while (!HMin[n].empty())
    {
        fout << *HMin[n].begin() << ' ';
        HMin[n].erase(HMin[n].begin());
    }
    fout << '\n';
    fout.close();
    return 0;
}