#include <cstdio>
using namespace std;
struct graf
{
    unsigned short x,l;
    graf *u;
};
graf *g[50001];
int d[50001];
void bag(unsigned short a,unsigned short b,unsigned short l)
{
    graf *q = new graf;
    q->x=b;
    q->l=l;
    q->u=g[a];
    g[a]=q;
}
int main()
{
    unsigned short n,a,b,l,poz;
    int m,i,cmin;
    graf *p,*q;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%hu%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%hu%hu%hu",&a,&b,&l);
        if(a==1) d[b]=l;
         bag(a,b,l);
    }

    while(g[1]!=NULL)
    {
        cmin=g[1]->l;
        q=g[1];
        while(q->u!=NULL)
        {
            if(q->u->l<cmin)
            {
                cmin=q->u->l;
                p=q;
            }
            q=q->u;
        }
        if(cmin!=g[1]->l)
        {
            poz=p->u->x;
            p->u=p->u->u;
        }
        else
        {
            poz=p->x;
            g[1]=g[1]->u;
        }
            q=g[poz];
            while(q!=NULL)
            {
                if(d[q->x]==0)

                {
                    d[q->x]=cmin+q->l;
                    bag(1,q->x,d[q->x]);
                }
                else if (d[q->x]>cmin+q->l)
                {
                    d[q->x]=cmin+q->l;
                    p=g[1];
                    while(p->x!=q->x)
                    p=p->u;
                    p->l=cmin+q->l;
                }
                q=q->u;
            }

    }
    for(i=2;i<n;++i)
    printf("%d ",d[i]);
    printf("%d\n",d[n]);
    return 0;
}