#include<iostream>
#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX=50001;
const int MMAX=250001;
const int inf=1<<30;
int coada[MMAX],d[NMAX];
struct lista
{
    int v;
    int c;
    lista *urm;
};
lista *nou,*cap[NMAX];
int n,m;
void dijkstra(int ns)
{   int i,pi,ps,nod,v,c;
    for(i=1;i<=n;i++)
    d[i]=inf;
    d[ns]=0;
    coada[1]=ns;
    pi=1;
    ps=1;
    while(pi<=ps)
    {   nod=coada[pi];
        nou=cap[nod];
        while(nou!=NULL)
        {   v=nou->v;
            c=nou->c;
            if(d[v]>c+d[nod])
            {   ps++;
                d[v]=c+d[nod];
                coada[ps]=v;
            }
            nou=nou->urm;
        }
            pi++;

        }

    }



int main()
{   int a,b,c,i;
    in>>n;
    in>>m;
    for(i=1;i<=m;i++)
    {   in>>a>>b>>c;
        nou=new lista;
        nou->v=b;
        nou->c=c;
        nou->urm=cap[a];
        cap[a]=nou;

    }

   /*for(i=1;i<=n;i++)
   {   nou=cap[i];
        out<<i<<":"<<" ";
        while(nou!=NULL)
        {   out<<nou->v<<" ";
        nou=nou->urm;

        }
        out<<endl;

   }*/
   dijkstra(1);
   for(i=2;i<=n;i++)
    out<<d[i]<<" ";
    return 0;
}