#include<cstdio>
#include<vector>

using namespace std;

int nod,d[50002],x,y,c,i,m,n,h[50002],st,dr,p[50002];
vector< pair<int,int> > g[50002];
vector< pair<int,int> >::iterator q;

void swap(int i,int j)
{
    int x;
    x=h[i];
    h[i]=h[j];
    h[j]=x;
    x=p[h[i]];
    p[h[i]]=p[h[j]];
    p[h[j]]=x;
}

void heapup(int nod)
{
    if(d[h[nod/2]]<d[h[nod]])
    {
        return;
    }
    swap(nod,nod/2);
    heapup(nod/2);
}

void heapdown(int nod)
{
    if(nod*2>m)
    {
        return;
    }
    st=d[h[i*2]];
    if(i*2+1<=m)
    {
        dr=d[h[i*2+1]];
    }
    else
    {
        dr=st+1;
    }
    if(st<dr)
    {
        if(d[h[i]]<=st)
        {
            return;
        }
        swap(i*2,i);
        heapdown(i*2);
    }
    else
    {
        if(d[h[i]]<=dr)
        {
            return;
        }
        swap(i*2+1,i);
        heapdown(i*2+1);
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++)
    {
        d[i]=400000000;
        h[i]=i;
        p[i]=i;
    }
    m=n;
    d[1]=0;
    d[0]=-1;
    for(i=0;i<n;i++)
    {
        nod=h[1];
        swap(1,m);
        m--;
        heapdown(1);
        for(q=g[nod].begin();q!=g[nod].end();q++)
        {
            if(d[(*q).first]>d[nod]+(*q).second)
            {
                d[(*q).first]=d[nod]+(*q).second;
                heapup(p[(*q).first]);
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]!=200000000)
        {
            printf("%d",d[i]);
        }
        else
        {
            printf("0");
        }
        if(i<n)
        {
            printf(" ");
        }
        else
        {
            printf("\n");
        }
    }
    return 0;
}