#include <stdio.h>

using namespace std;

int n,m,ncr,poz=0,bufflen=1,vft=0;
char buff[1000005];

struct mucost{
    int vecin,cost;
};

int ls[50005],urm[250005];
mucost vf[250005];

int d[50005],heap[50005],v[50005];

void swagg(int i, int j)
{
    int aux;
    aux=heap[i];
    heap[i]=heap[j];
    heap[j]=aux;
    v[heap[i]]=i;
    v[heap[j]]=j;
}

int read()
{
    int x=0;
    while(buff[poz]<'0'||buff[poz]>'9')
    {
        poz++;
        if(bufflen==poz) {poz=0;bufflen=fread(buff,1,1000000,stdin);}
    }
    while(buff[poz]>='0'&&buff[poz]<='9')
    {
        x=x*10+buff[poz]-'0';
        poz++;
        if(bufflen==poz) {poz=0;bufflen=fread(buff,1,1000000,stdin);}
    }
    return x;
}

void add_ls(int x, int y, int cost)
{
    vft++;
    vf[vft]=(mucost){y,cost};
    urm[vft]=ls[x];
    ls[x]=vft;
}

void heapup(int k)
{
    int i;
    while(k>1)
    {
        i=k>>1;
        if(d[heap[i]]>d[heap[k]]) {swagg(i,k);k=i;}
        else break;
    }
}

int heapdown()
{
    int i,j;
    swagg(1,ncr);
    ncr--;
    i=1;
    while(2*i<=ncr)
    {
        j=2*i;
        if(j+1<=ncr&&d[heap[j]]>d[heap[j+1]]) j++;
        if(d[heap[i]]>d[heap[j]]) {swagg(i,j);i=j;}
        else break;
    }
    return heap[ncr+1];
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,j,a,b,c;
    n=read();
    m=read();
    ncr=n;
    for(i=0;i<m;i++)
    {
        a=read();
        b=read();
        c=read();
        add_ls(a,b,c);
    }
    v[1]=1;
    heap[1]=1;
    for(i=2;i<=n;i++)
    {
        d[i]=2000000000;
        heap[i]=i;
        v[i]=i;
    }

    for(i=0;i<n;i++)
    {
        a=heapdown();
        c=ls[a];
        while(c!=0)
        {
            b=vf[c].vecin;
            j=d[a]+vf[c].cost;
            if(d[a]!=2000000000&&d[b]>j)
            {
                d[b]=j;
                heapup(v[b]);
            }
            c=urm[c];
        }
    }

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