#include <fstream>
#include<climits>
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
struct bla
{
      int nod,urm,cost;
} t[500010];
int start[50010];
int d[50010],w;
int poz_heap[50010];
int n,m,heap[50010];
void read ()
{ int a,b,c,k=0;
      cin>>n>>m;
      for(int i=1;i<=m;i++)
      {
            cin>>a>>b>>c;
            t[++k].nod=b; t[k].urm=start[a];start[a]=k; t[k].cost=c;
      }
}
void init ()
{
      for(int i=2;i<=n;i++)
            d[i]=INT_MAX;
}
void climb (int poz)
{
      while(3>2)
      {
            if(poz>1 && d[heap[poz]]<d[heap[poz/2]])
                  swap(heap[poz],heap[poz/2]),poz_heap[heap[poz]]=poz,poz_heap[heap[poz/2]]=poz/2,poz/=2;
            else break;
      }
}
void down (int poz)
{
      while(3>2)
      {
            int fiu=0;
            if(poz*2<=w) fiu=poz*2;
            if(fiu+1<=w && d[heap[fiu+1]]<d[heap[fiu]]) fiu++;
            if(fiu && d[heap[poz]]>d[heap[fiu]])
                  swap(heap[poz],heap[fiu]),poz_heap[heap[poz]]=poz,poz_heap[heap[fiu]]=fiu,poz=fiu;
            else break;
      }
}
void dijkstra ()
{
      heap[++w]=1;
      poz_heap[1]=1;
      while(w)
      {
            int varf=heap[1];
            heap[1]=heap[w--];
            poz_heap[heap[1]]=1;
            down(1);
            for(int x=start[varf];x;x=t[x].urm)
                  if(d[varf]+t[x].cost<d[t[x].nod])
                  {
                       d[t[x].nod]=d[varf]+t[x].cost;
                       if(poz_heap[t[x].nod]!=0)
                        climb(poz_heap[t[x].nod]);
                       else heap[++w]=t[x].nod,poz_heap[heap[w]]=w,climb(w);
                  }
      }
}
void write ()
{
      for(int i=2;i<=n;i++)
      {
            if(d[i]==INT_MAX) d[i]=0;
            cout<<d[i]<<" ";
      }
}
int main()
{
    read();
    init();
    dijkstra();
    write();
    cin.close();
    cout.close();
    return 0;
}