#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct lista
{
    int nod,c;
    lista *urm;
};
lista *a[50001],*q;
int h[50001],d[50001],p[50001],n,m;
void creare(int x,int y,int c)
{
    q=new lista;
    q->nod=y;
    q->c=c;
    q->urm=a[x];
    a[x]=q;
}
void schimba(int x,int y)
{
    int aux;
    aux=h[x];
    h[x]=h[y];
    h[y]=aux;
    aux=p[h[x]];
    p[h[x]]=p[h[y]];
    p[h[y]]=aux;
}
void heapup(int x)
{
    if(d[h[x/2]]<d[h[x]])
    {
        return;
    }
    else
    {
        schimba(x/2,x);
        heapup(x/2);
    }
}
void heapdown(int x)
{
    int st,dr;
    if(x*2>m)
    {
        return;
    }
    else
    {
        st=d[h[2*x]];
        if(x*2+1<=m)
        {
            dr=d[h[2*x+1]];
        }
        else
        {
            dr=st+1;
        }
        if(st<dr)
        {
            if(d[h[x]]<=st)
            {
                return;
            }
            else
            {
                schimba(x,2*x);
                heapdown(2*x);
            }
        }
        else
        {
            if(d[h[x]]<=dr)
            {
                return;
            }
            else
            {
                schimba(x,2*x+1);
                heapdown(2*x+1);
            }
        }
    }
}
int main()
{
    int x,y,c,i,v;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        creare(x,y,c);
    }
    for(i=1;i<=n;i++)
    {
        h[i]=i;
        p[i]=i;
        d[i]=2000000001;
    }
    m=n;
    d[1]=0;
    d[0]=-1;
    for(i=0;i<n;i++)
    {
        v=h[1];
        schimba(1,m);
        m--;
        heapdown(1);
        for(q=a[v];q!=NULL;q=q->urm)
        {
            if(d[q->nod]>d[v]+q->c)
            {
                d[q->nod]=d[v]+q->c;
                heapup(p[q->nod]);
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==2000000001)
        {
            g<<0<<" ";
        }
        else
        {
            g<<d[i]<<" ";
        }
    }
    return 0;
}