#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <fstream>
#define INF 0x3f3f3f3f
#define N 50001
#define M 500001
#define st(x) 2*(x)
#define dr(x) 2*(x)+1
#define pr(x) (x)/2
using namespace std;
struct nod{long nod,cost,urm;}v[M];
long h[N],ph[N],cost[N],p[N],vf;
int s[N];//multimea cu nodurile pentru care s-a stabilit lungimea minima
void adauga(long a,long b,long c)
{++vf;
 v[vf].urm=p[a];
 p[a]=vf;
 v[vf].nod=b;
 v[vf].cost=c;
}

void relax(long u)
{long q,aux,i;
 for (q=p[u];q;q=v[q].urm)
 {if(s[v[q].nod]==0&&cost[v[q].nod]>cost[u]+v[q].cost)
  {cost[v[q].nod]=cost[u]+v[q].cost;
   for (i=ph[v[q].nod];pr(i)&&cost[h[i]]<cost[h[pr(i)]];i=pr(i))
   {aux=h[i];h[i]=h[pr(i)];h[pr(i)]=aux;
    ph[h[i]]=i;ph[h[pr(i)]]=pr(i);
   }
  }
 }
}

void sift(long u)
{long aux, son=u;
 if(st(u)<=h[0]&&cost[st(u)]<cost[son])
 {son=st(u);
 }
 if(dr(u)<=h[0]&&cost[dr(u)]<cost[son])
 {son=dr(u);
 }
 if(son!=u)
 {aux=h[son];h[son]=h[u];h[u]=aux;
  ph[h[son]]=son;
  ph[h[u]]=u;
  sift(son);
 }
}

void scoate()//varful hului
{h[1]=h[h[0]];h[0]--;
 ph[h[1]]=1;
 sift(1);
}

int main ()
{long n,m,a,b,c,i,min;
 ifstream fin("dijkstra.in");
 ofstream fout("dijkstra.out");
 fin>>n>>m;
 for (i=0;i<m;i++)
 {fin>>a>>b>>c;
  adauga(a,b,c);
 }
 for (i=1;i<=n;i++)
 {s[i]=0;}
 
 s[1]=1;
 for (i=1;i<n;i++)
 {h[i]=i+1;
  ph[i+1]=i;
 }
 
 h[0]=n-1;
 cost[1]=0;
 for (i=2;i<=n;i++)
 {cost[i]=INF;
 }
 
 relax(1);
 for (i=1;i<n;i++)
 {min=h[1];
  s[min]=1;
  scoate();//din h
  relax(min);
 }
 for (i=2;i<=n;i++)
 {fout<<((cost[i]<INF)?cost[i]:0)<<" ";
 }
 fout.close();
 return 0;
}