#include <fstream>
#include <vector>
using namespace std;
#define NMAX 50001
#define inf 1<<30
#define start 1
vector<int> l[NMAX],c[NMAX];
long d[NMAX];
int h[NMAX],n,k,poz[NMAX];
inline void swap(int &x,int &y)
 {
 int ax=x;
 x=y;
 y=ax;
 }
void downheap(int nod)
 {
 int i=nod<<1;
 while(i<=k)
  {
  if(i+1<=k&&d[h[i+1]]<d[h[i]])
   ++i;
  if(d[h[nod]]>d[h[i]])
   {
   swap(h[nod],h[i]);
   poz[h[nod]]=nod;
   poz[h[i]]=i;
   }
  else
   return;
  }
 }
void upheap(int nod)
 {
 int i=nod>>1;
 while(i&&d[h[nod]]<d[h[i]])
  {
  swap(h[i],h[nod]);
  poz[h[i]]=i;
  poz[h[nod]]=nod;
  nod=i;
  i=i>>1;
  }
  
 }
void read()
 {
 int m,i,x,y,cost;
 ifstream f("dijkstra.in");
 f>>n>>m;
 for(i=1;i<=m;i++)
  {
  f>>x>>y>>cost;
  l[x].push_back(y);
  c[x].push_back(cost);
  }
 for(i=1;i<=n;i++)
 {
 poz[i]=-1;
  if(i==start)
   d[i]=0;
  else
   d[i]=inf;
 }
 }
void solve()
 {
 int x,i,y;
 h[++k]=start;
 poz[h[k]]=k;
 while(k>0)
  {
  x=h[1];
  swap(h[1],h[k]);
  poz[h[1]]=1;
  --k;
  downheap(1);
  for(i=0;i<l[x].size();i++)
   {
   y=l[x][i];
   if(d[y]>d[x]+c[x][i])
    {
    d[y]=d[x]+c[x][i];
	if(poz[y]!=-1)
	 upheap(poz[y]);
	else
	 {
	 h[++k]=y;
	 poz[h[k]]=k;
	 upheap(k);
	 }
    }
   }
  }
 }
void show()
 {
 ofstream g("dijkstra.out");
 for(int i=1;i<=n;i++)
  {
  if(i==start)
   continue;
  g<<((d[i]==inf)?(0):(d[i]))<<" ";
  }
 }
int main()
 {
 read();
 solve();
 show();
 }