vacanta2020

#include <bits/stdc++.h>
using namespace std;
ifstream f("vacanta2020.in");
ofstream g("vacanta2020.out");
vector < pair <int,int> > G[460110];
long long dist[460110];
bool viz[460110];
int n,m,vouch;
typedef pair <int,int> p;
priority_queue <p, vector <p> , greater<p> > Q;
# define INF 10000000000000000
void read()
{
    f>>n>>m>>vouch;
    int a,b,c;
    for(int i=1;i<=m;++i)
    {

        f>>a>>b>>c;
        for(int j=0;j<=vouch;++j)
        {
            G[a+j*n].push_back({c,b+j*n});
            G[b+j*n].push_back({c,a+j*n});
            if(j!=vouch+1)
            {
                G[a+j*n].push_back({0,b+(j+1)*n});
                G[b+j*n].push_back({0,a+(j+1)*n});
            }
		}
	}
}
void init()
{
    for(int i=1;i<=n*(vouch+1);++i)
    {
        dist[i]=INF;
        if(i%(n+1)==0)
            dist[i]=0;
    }
	dist[1]=0;
}

void Dijkstra()
{
    int vert;
    while(!Q.empty())
    {
        if(viz[Q.top().second])
            Q.pop();
        else
        {
            vert=Q.top().second;
            viz[vert]=true;
            for(int i=0;i<G[vert].size();++i)
            {
                if(dist[G[vert][i].second]>dist[vert]+G[vert][i].first)
                {
                    dist[G[vert][i].second]=dist[vert]+G[vert][i].first;
                    Q.push(make_pair(G[vert][i].first+dist[vert],G[vert][i].second));


                }
            }
        }
    }

}

int main()
{
    read();
    init();
    Q.push(make_pair(0,1));
    Dijkstra();
    for(int i=n*vouch+1;i<=n*(vouch+1);++i)
    	g<<dist[i]<<" ";
	return 0;
}