#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;

FILE *f;
FILE *g;

typedef struct nod
{
    int inf,c;
    nod *urm;
} NOD;
typedef NOD *graf[50010];
graf G;

NOD *p,*q;

int n,m,d[50010],C[500010],pr,ul;
bool v[50010];

void citire()
{
    f=fopen("dijkstra.in","r");
    fscanf(f,"%d %d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        p=new NOD;
        p->inf=b; p->urm=G[a]; p->c=c;
        G[a]=p;
    }
    fclose(f);
}

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



int main()
{
    citire();
    init();
    while(pr<=ul)
    {
        p=G[C[pr]];
        v[C[pr]]=false;
        while(p)
        {
            if(d[p->inf]>d[C[pr]]+p->c)
            {
                d[p->inf]=d[C[pr]]+p->c;
                if(!v[p->inf])
                {
                    C[++ul]=p->inf;
                    v[p->inf]=true;
                }
            }
            p=p->urm;
        }
        pr++;
    }
    g=fopen("dijkstra.out","w");
    for(int i=2;i<=n;i++)
        fprintf(g,"%d ",d[i]<INF?d[i]:0);
    fprintf(g,"\n");
    fclose(g);
    return 0;
}