#include <cstdio>
#include <fstream>
# define MX 50005
using namespace std;
struct lista
		{ int x,c;
		  lista *urm;
		};
lista *p[MX];
int n,i,x,tata[MX],Inf=999999999;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void formare()
{ int i,j,k,c,m;
  lista *ultim[MX],*q;
  f>>n>>m;
  x=1;
  for (i=1; i<=n; i++)
	  { p[i]=new lista;
		p[i]->x=0;
		p[i]->c=0;
		p[i]->urm=NULL;
		ultim[i]=p[i];
	  }
	for (k=1; k<=m; k++)
		{ f>>i>>j>>c;
			//fscanf(f, "%d%d%d", &i, &j, &c);
		  q=new lista;
		  q->x=j;
		  q->c=c;
		  q->urm=NULL;
		  ultim[i]->urm=q;
		  ultim[i]=q;
		}
	for (i=1; i<=n; i++)
		{   q=p[i];
			p[i]=p[i]->urm;
			delete q;
		}
}
void afis(int i)
{ lista *q;
  q=p[i];
  while (q)
	  { g<<q->x<<'-'<<q->c<<"->";
        q=q->urm;
	  }
  g<<"NULL"<<"\n";
}
/*void af()
{ int i;
  for (i=1; i<=n; i++)
	  if (i!=x) g<<d[i]<<' ';
  g<<'\n';
}*/
void dijkstra()
{ int i,k,min, vf_min=-1;
  lista *q;
  int d[MX], viz[MX];
  for (i=1; i<=n; i++)
	  { d[i]=Inf;
        tata[i]=x;
		viz[i]=0;
	  }
   d[x]=0;
   viz[x]=1;
   tata[x]=0;
   q=p[x];
   while (q)
	   { d[q->x]=q->c;
		 q=q->urm;
	   }
	//af(d);
	//af(tata);
	//af(viz);
	//g<<"............................................."<<'\n';
	for (k=1; k<n; k++)
	   { min=Inf;
	     for (i=1; i<=n; i++)
			 if (viz[i]==0 && d[i]<min) 
					 { min=d[i];
					   vf_min=i;
					 }
		 viz[vf_min]=1;
		 q=p[vf_min];
		 while (q)
				   { if(!viz[q->x] && d[q->x]>min+q->c) { tata[q->x]=vf_min;
												          d[q->x]=min+q->c;
												      }
					 q=q->urm;  
				   }
		 //af(d);
		 //af(tata);
		 //af(viz);
		 //g<<"............................................."<<'\n';
	   } 
    for (i=1; i<=n; i++)
	  if (i!=x) g<<d[i]<<' ';
  //g<<"\n";	   
}
/*void aff(int i)
{ int j,k,v[50000];
  j=tata[i];
  k=0;
  while (tata[j]!=0)
		{ v[++k]=j;
		  j=tata[j];
		}
   g<<x<<' ';
   for (j=k; j>=1; j--)
	   g<< v[j]<<' ';
   g<<i<<' '<<'\n';
}*/
int main()
{ formare();
   dijkstra();
   //for (i=1; i<=n; i++)
	  //if (i!=x) aff(i);
				
  return 0;
}