#include <fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,co[50002],viz[50002],inainte[50002];
int Q[50002],incep,sf;


struct nod {
    int x;
    int cost;
    nod *urm;
} *L[101];

int main()
{    
	nod *p,*q;
    int i,a,b,c,s,t,u;
    f>>n>>m;
    s=1;
    //Citirea liste
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        p=new nod;
        p->x=b;
        p->cost=c;
        p->urm=L[a];
        L[a]=p;
        //Doar daca e graf neorientat
        q=new nod;
        q->x=a;
        q->cost=c;
        q->urm=L[b];
        L[b]=q;       
    }
    //Initializari
    for(i=1;i<=n;i++)
    {	
        viz[i]=0;
        inainte[i]=s;
        co[i]=-1;
    }
    viz[s]=1;
    co[s]=0;
    inainte[s]=0;

	//Algoritmul propriuzis
	int min=20000,ii;
	incep=1;
	sf=0;
    Q[++sf]=s;
    while(incep<=sf)
    {		
		min=20000;
        u=Q[incep];
		p=L[u];
		viz[u]=1;		
		while(p)
		{
			if(!viz[p->x] && co[p->x] > co[u] + p->cost || co[p->x]==-1)
			{
				co[p->x]=co[u] + p->cost;
				inainte[p->x]=u;
			}				
			if(min>p->cost && !viz[p->x])
				min=p->cost,ii=p->x;
			p=p->urm;
		}
		incep++;
		if(Q[sf]!=ii)
			Q[++sf]=ii;
	}
	//Afiseaza doar vectorul inainte
	for(i=2;i<=n;i++)
		g<<co[i]<<' ';
    f.close();
    g.close();
    return 0;	
}