#include <cstdio>
#define pinf 100000000
#define NMAX 50003
using namespace std;
FILE *fin=fopen("dijkstra.in","r");
FILE *fout=fopen("dijkstra.out","w");
struct nod
{
    int urm,cost;
    nod *next;
};
nod *p,*l[50003];
unsigned int x,y,i,j,n,coada[5*NMAX],d[NMAX],m;
int main()
{
    fscanf(fin," %d %d ",&n ,&m);
    int pr,u;
    for(i=1;i<=m;++i)
    {
        p=new nod;
        fscanf(fin," %d %d %d",&x,&p->urm,&p->cost);
        p->next=l[x];
        l[x]=p;
    }
    pr=1;u=1;
    coada[u]=1;
    for(i=1;i<=n;++i)
            d[i]=pinf;
    d[1]=0;
    while(pr<=u)
    {
        x=coada[pr];
        pr++;
        p=new nod;
        p=l[x];
        while(p)
        {

                if(d[x]+p->cost<d[p->urm])
                    {
                        d[p->urm]=d[x]+p->cost;
                        coada[++u]=p->urm;
                    }
            p=p->next;
        }
    }
    for(i=2;i<=n;++i)
        if(d[i]==pinf)
            fprintf(fout,"0 ");
        else
            fprintf(fout,"%d ",d[i]);
    return 0;
}