#include<fstream>
using namespace std;

int n,m,i,j,x,y,c,nod;
int H[50002],p[50002],d[50002],t[50002];
struct graf{
    int x,c;
    graf *urm;
};
graf *gr[50002],*q;
int inf=2000000000;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void add(int x,int y,int c)
{
    graf *q=new graf;
    q->x=y;
    q->c=c;
    q->urm=gr[x];
    gr[x]=q;
}

void swap(int i,int j)
{
    int aux;
    aux=H[i];H[i]=H[j];H[j]=aux;
    aux=p[H[i]];p[H[i]]=p[H[j]];p[H[j]]=aux;
}

void up(int k)
{
    if(d[H[k/2]]<d[H[k]]) return;
    swap(k,k/2);
    up(k/2);
}

void down(int k)
{
    /*int st,dr;
    if(2*k>m) return;
    st=d[H[2*k]];
    if(2*k+1<=m) dr=d[H[2*k+1]];
        else dr=st+1;
    if(st<dr)
    {
        if(d[H[k]]<=st) return;
        swap(k,2*k);
        down(2*k);
    }
    else
    {
        if(d[H[k]]<=dr) return;
        swap(k,2*k+1);
        down(2*k+1);
    }*/
    int fiu=2*k,tata=k;
    while(fiu<=m)
    {
        if(fiu+1<=m && d[H[fiu]]>d[H[fiu+1]]) fiu++;
        if(d[H[fiu]]<d[H[tata]])
        {
            swap(fiu,tata);
            tata=fiu;
            fiu=2*tata;
        }
        else fiu=m+1;
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        add(x,y,c);
    }

    for(i=1;i<=n;i++)
    {
        d[i]=inf;
        H[i]=i;
        p[i]=i;
    }

    m=n;
    d[1]=0;
    d[0]=-1;
    for(i=1;i<n;i++)
    {
        nod=H[1];
        swap(1,m);
        m--;
        down(1);
        for(q=gr[nod];q!=NULL;q=q->urm)
        {
            if(d[q->x]>d[nod]+q->c)
            {
                d[q->x]=d[nod]+q->c;
                t[q->x]=nod;
                up(p[q->x]);
            }
        }
    }

    for(i=2;i<=n;i++)
    {
        if(d[i]==inf) g<<0<<" ";
        else g<<d[i]<<" ";
    }

    f.close();
    g.close();
    return 0;
}