#include <cstdio>
#define INF 2000000000
using namespace std;

typedef struct NOD
{
    int inf,c;
    NOD *urm;
} nod;

typedef nod *graf[50010];
graf g;

FILE *F;
FILE *G;

int n,m;
int d[50010],viz[50010];

void citire()
{
    F=fopen("dijkstra.in","r");
    fscanf(F,"%d %d",&n,&m);
    nod *p;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fscanf(F,"%d %d %d",&x,&y,&c);
        p=new nod; p->urm=g[x]; p->inf=y; p->c=c; g[x]=p;
    }
    fclose(F);
}

void init()
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
}

int detmin()
{
    int minn=INF,k=0;
    for(int i=1;i<=n;i++)
        if(d[i]<minn&&!viz[i])
        {
            minn=d[i];
            k=i;
        }
    return k;
}
void dijkstra()
{
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        int k=detmin();
        viz[k]=1;
        nod *p;
        p=g[k];
        while(p)
		{
            if(!viz[p->inf])
                if(d[k]+p->c<d[p->inf])
                    d[p->inf]=d[k]+p->c;
            p=p->urm;
        }
    }
}

int main()
{
    citire();
    init();
    dijkstra();
	G=fopen("dijkstra.out","w");
	for(int i=2;i<=n;i++)
		if(d[i]==INF)
			fprintf(G,"0 ");
		else
			fprintf(G,"%d ",d[i]);
	fprintf(G,"\n");
	fclose(G);
    return 0;
}