#include <cstdio>
using namespace std;

int h=0,viz[50000],heap[50002],d[50000];

struct graf
{
    int v,c;
    graf *u;
}*nod[50000];

void init(graf *&x)
{
    x=new graf;
    x->u=NULL;
}

graf *next(graf *&x)
{
    graf *x1,*x2;
    x1=x;
    if(x1)
    {
        while(x1->u!=NULL) x1=x1->u;
        init(x2);
        x1->u=x2;
        return x2;
    }
    init(x);
    return x;
}

/*void parcurgere_adancime(graf *x,int y)
{
    while(x!=NULL)
    {
        printf("%d %d %d\n",y+1,x->v+1,x->c);
        parcurgere_adancime(nod[x->v],x->v);
        x=x->u;
    }
}*/

void urca(int i)
{
    int aux=heap[i];
    while(i>1&&d[heap[i]]<d[heap[i/2]])
    {
        heap[i]=heap[i/2];
        i/=2;
    }
    heap[i]=aux;
}

void coboara(int i)
{
    int j,aux;
    do
    {
        j=0;
        if(i*2<=h)
        {
            j=i*2;
            if(d[heap[j]]>d[heap[i*2+1]]&&i*2+1<=h) j=i*2+1;
            if(d[heap[j]]>d[heap[i]]) j=0;
        }
        if(j)
        {
            aux=heap[j];
            heap[j]=heap[i];
            heap[i]=aux;
            i=j;
        }
    }
    while(j);
}

void buildheap()
{
    int i;
    for(i=h/2;i>0;--i)
    {
        coboara(i);
    }
}

void adauga(int i)
{
    heap[++h]=i;
    urca(h);
}

void sterge(int i)
{
    heap[i]=heap[h--];
    if(i>1&&d[heap[i]]<d[heap[i/2]]) urca(i);
    else coboara(i);
}

int cauta(int x,int n)
{
    if(heap[n]==x) return n;
    else
    {
        if(n*2<=h)
        {
            if(d[x]>=d[heap[n*2]]) cauta(x,n*2);
        }
        if(n*2+1<=h)
        {
            if(d[x]>=d[heap[n*2+1]]) cauta(x,n*2+1);
        }
    }
}

void showheap()
{
    int y=2;
    for(int i=1;i<=h;++i)
    {
        printf("%d ",heap[i]);
        if(i==y-1)
        {
            printf("\n");y*=2;
        }
    }
    printf("\n\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,j;
    graf *nod1;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%d",&j);
        nod1=next(nod[j-1]);
        scanf("%d",&j);
        nod1->v=j-1;
        scanf("%d",&j);
        nod1->c=j;
    }
    // parcurgere_adancime(nod[0],0);
    for(i=1;i<n;++i)
    {
        d[i]=250000001;
    }
    d[0]=0;
    nod1=nod[0];
    while(nod1)
    {
        d[nod1->v]=nod1->c;
        viz[nod1->v]=1;
        heap[++h]=nod1->v;
        nod1=nod1->u;
    }
    viz[0]=2;
    buildheap();
    while(h)
    {
        nod1=nod[heap[1]];
        while(nod1)
        {
           // showheap();
            if(!viz[nod1->v])
            {
                d[nod1->v]=d[heap[1]]+nod1->c;
                adauga(nod1->v);
                viz[nod1->v]=1;
            }
            else if(viz[nod1->v]==1)
                 {
                     i=cauta(nod1->v,1);
                     j=d[heap[1]]+nod1->c;
                     if(d[nod1->v]>j)
                     {
                         d[nod1->v]=j;
                         urca(i);
                     }
                 }
            nod1=nod1->u;
        }
        viz[heap[1]]=2;
        sterge(1);
    }
    for(i=1;i<n;++i)
    {
        if(d[i]==250000001) printf("0 ");
        else printf("%d ",d[i]);
    }
    printf("\n");
    return 0;
}