#include <fstream>
#define INF 2000000000
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
struct lista
{
    int c,nod;
    lista *urm;
} *g[50001],*p;
int x,y,z,n,m,d[50001],h[50001],nh,poz[50001];
//int n,m,pr,loc[2000],nh,d[2001],h[2001],poz[2001],dl[2001][2001],s,sol=INF,use[2001],contor;
/*void citire ()
{
    int x,y,z,i;
    fin>>n>>m>>pr;
    for (i=1;i<=pr;i++)
        fin>>loc[pr];
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        p=new lista;
        p->urm=g[x];
        p->nod=y;
        p->c=z;
        g[x]=p;
        p=new lista;
        p->urm=g[y];
        p->nod=x;
        p->c=z;
        g[y]=p;
    }
    fin.close ();
}*/
void heapdown (int k)
{
    int st,dr,i,cd=d[h[k]],ck=h[k];
    while (k<nh)
    {
        st=k*2;
        if (st<=nh)
        {
            dr=k*2+1;
            if (dr<=nh)
                if (d[h[st]]<d[h[dr]])
                    i=st;
                else i=dr;
            else i=st;
            if (d[h[i]]<cd)
            {
                h[i/2]=h[i];
                poz[h[i]]=i/2;
                k=i;
            }
            else break;
        }
        else break;
    }
    h[k]=ck;
    poz[ck]=k;
}
void heapup (int k)
{
    int ck=h[k],cd=d[h[k]];
    while (k>1&&cd<d[h[k/2]])
    {
        h[k]=h[k/2];
        poz[h[k]]=k;
        k/=2;
    }
    h[k]=ck;
    poz[ck]=k;
}
void buildh ()
{
    for (int i=2;i<=n;i++)
        heapup (i);
}
int extragemin ()
{
    int aux;
    aux=h[1];
    h[1]=h[nh];
    poz[h[1]]=1;
    poz[aux]=0;
    nh--;
    heapdown (1);
    return aux;
}
void dijkstra (int sursa)
{
    int i,nod;
    for (i=1;i<=n;i++)
    {
        d[i]=INF;
        h[i]=i;
        poz[i]=i;
    }
    d[sursa]=0;
    nh=n;
    buildh ();
    while (nh)
    {
        nod=extragemin();
        for (p=g[nod];p;p=p->urm)
        {
            if (d[p->nod]>d[nod]+p->c)
            {
                d[p->nod]=d[nod]+p->c;
                heapup (poz[p->nod]);
            }
        }
    }
}
/*void ad (int oras)
{
    int i;
    if (contor==pr)
    {
        if (s+dl[oras][n]<sol)
            sol=s+dl[oras][n];
        return;
    }
    for (i=1;i<=pr;i++)
        if (!use[i])
        {
            contor++;
            use[i]=1;
            s+=dl[oras][loc[i]];
            ad(loc[i]);
            s-=dl[oras][loc[i]];
            use[i]=0;
            contor--;
        }
}*/
int main()
{
    int i,j;
    //citire ();
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        p=new lista;
        p->urm=g[x];
        p->nod=y;
        p->c=z;
        g[x]=p;
    }
    dijkstra(1);
    /*for (i=1;i<=n;i++)
    {
        dijkstra (i);
        for (j=1;j<=n;j++)
            dl[i][j]=d[j];
    }
    //ad (1);
    //fout<<sol<<'\n';*/
    for (i=2;i<=n;i++)
    {
        if (d[i]==2000000000) fout<<0<<' ';
        else fout<<d[i]<<' ';
    }
    fout<<'\n';
    fout.close ();
    return 0;
}