#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;
bool F[1024];
vector < pair < int, int > > G[1024];
vector < int > L[1024];
multiset < int, cmp1 > HMin[1024];
multiset < int, cmp2 > HMax[1024];

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 } );
    }
    HMin[1].insert(0);
    HMax[1].insert(0);
    L[l].push_back(1);
    F[1] = true;
    while (L[l][0] != n)
    {
        l ++;
        for (vector < int > :: iterator it1 = L[l - 1].begin(); it1 != L[l - 1].end(); it1 ++)
        {
            while (!HMin[*it1].empty())
            {
                int dmin = *HMin[*it1].begin();
                HMin[*it1].erase(HMin[*it1].begin());

                for (vector < pair < int, int > > :: iterator it2 = G[*it1].begin(); it2 != G[*it1].end(); it2 ++)
                {
                    if (!F[it2->first])
                    {
                        F[it2->first] = true;
                        L[l].push_back(it2->first);
                    }

                    if (HMin[it2->first].size() < k)
                    {
                        HMin[it2->first].insert(dmin + it2->second);
                        HMax[it2->first].insert(dmin + it2->second);
                    }
                    else if (dmin + it2->second < *HMax[it2->first].begin())
                    {
                        HMin[it2->first].insert(dmin + it2->second);
                        HMin[it2->first].erase(HMin[it2->first].find(*HMax[it2->first].begin()));
                        HMax[it2->first].insert(dmin + it2->second);
                        HMax[it2->first].erase(HMax[it2->first].begin());
                    }
                }
            }
        }
    }
    while (!HMin[n].empty())
    {
        fout << *HMin[n].begin() << ' ';
        HMin[n].erase(HMin[n].begin());
    }
    fout.close();
    return 0;
}