#include <fstream>
#include <vector>
#define nmax (1<<10)
#define oo (1<<30)
#define Vecin G[Nod][i].first
#define Cost G[Nod][i].second
using namespace std;

vector < pair<int,int> > G[nmax];
int N,K,L[nmax],A[nmax][nmax];
bool viz[nmax];

class HEAP {

    #define NMAxHeap nmax
    #define left(i) (2*i)
    #define right(i) (2*i+1)
    #define father(i) (i/2)
    #define cmp(a,b) (Dist[V[a]]<Dist[V[b]])

    private:
        int V[NMAxHeap],Loc[NMAxHeap],Vf;
    public:
        int Dist[NMAxHeap];
    public:
        HEAP():Vf(0){}
        void push(int,int);
        void pop();
        void update(int,int);
        int top();
        int size();
        void clear();
    private:
        void Up(int);
        void Down(int);

};
void HEAP::Up(int nod) {

    while(nod>1&&cmp(nod,father(nod))) {
        swap(V[nod],V[father(nod)]);
        swap(Loc[V[nod]],Loc[V[father(nod)]]);
        nod=father(nod);
        }

}
void HEAP::Down(int nod) {

    int son;
    do {
        son=0;
        if(left(nod)<=Vf) {

            son=left(nod);
            if(right(nod)<=Vf&&cmp(right(nod),son))
                son=right(nod);

            if(cmp(nod,son))
                son=0;
            }

        if(son) {
            swap(V[nod],V[son]);
            swap(Loc[V[nod]],Loc[V[son]]);
            nod=son;
            }

    }while(son);

}
void HEAP::push(int id,int Val) {

    V[++Vf]=id;
    Dist[id]=Val;
    Loc[id]=Vf;
    this->Up(Vf);

}
void HEAP::pop() {

    V[1]=V[Vf--];
    Loc[V[1]]=1;
    this->Down(1);

}
void HEAP::update(int id,int Val) {

    Dist[id]=Val;
    this->Up(Loc[id]);
    this->Down(Loc[id]);

}
int HEAP::top() {

    return V[1];

}
int HEAP::size() {

    return Vf;

}
void HEAP::clear() {

    Vf=0;

}
void DFS(int Nod) {

    int i,X=0;

    viz[Nod]=1;
	HEAP Heap;

    for(i=0;i<G[Nod].size();i++) {
        if(!viz[Vecin])
            DFS(Vecin);
        L[Vecin]=1;
        Heap.push(Vecin,A[Vecin][1]+Cost);
        }
	
	if(G[Nod].size())
    for(i=1;i<=K;i++) {
		
        X=Heap.top();
		
		if(A[X][L[X]]==oo)
			return;
		
        A[Nod][i]=Heap.Dist[X];
        Heap.update(X,Heap.Dist[X]-A[X][L[X]]+A[X][++L[X]]);
		
        }

}
void solve() {

    int i,j;

    for(i=1;i<=N;i++)
        for(j=1;j<=K;j++)
            A[i][j]=oo;

    A[N][1]=0;

    DFS(1);

}
void read() {

    int x,y,c,M;
    ifstream in("pitici.in");
    in>>N>>M>>K;

    while(M--) {

        in>>x>>y>>c;
        G[x].push_back(make_pair(y,c));

        }

    in.close();

}
void write() {
	
	ofstream out("pitici.out");
	
	for(int i=1;i<=K;i++)
		out<<A[1][i]<<' ';
	out<<'\n';
	
	out.close();
	
}
int main() {

    read();
    solve();
	write();

    return 0;

}