#include<fstream>
using namespace std;
#include<vector>

struct nod{
 int capat,cost;
 nod*next;};

nod *G[50005];
int n,m,v[50005],t[5005],d[50005];

void addarc(int i,int j,int c)
{
  nod*p=new nod;
  p->capat=j;
  p->cost=c;
  p->next=G[i]; 
  G[i]=p;
}
void init(int sursa)
 {
	for(int i=1;i<=n;i++)
     v[i]=0,t[i]=-1,d[i]=100000;
	v[sursa]=0;t[sursa]=0;d[sursa]=0;
	for(nod *p=G[sursa];p;p=p->next)
		t[p->capat]=sursa,d[p->capat]=p->cost;
}	
void dijktra(int sursa)
{
  init(sursa);
  int gata=0;
  while(!gata)
  {
	 int pmin=0;
     for(int i=1;i<=n;i++)
      if(v[i]==0 && d[i]<d[pmin])
        pmin=i;
     if(pmin==0)
       gata=1;
     else
	 {
		v[pmin]=1;
        for(nod *p=G[pmin];p;p=p->next)
           if(v[p->capat]==0)
			if(d[p->capat]>d[pmin]+p->cost)
              d[p->cost]=d[pmin]+p->cost,t[p->capat]=pmin;
	 }
  }
}
 
int main()
{
 ifstream fin("dijkstra.in");
int m;
fin>>n>>m;
for(;m;m--)
{	
	int i,j,c;
 fin>>i>>j>>c;
 addarc(i,j,c);
}
ofstream fout("dijkstra.out");
dijktra(1);
//for(int i=1;i<=n;i++)
	//fout<<t[i]<<" ";
for(int i=1;i<=n;i++)
	if(d[i]==100000)
		 fout<<"0"<<" ";
	else
	fout<<d[i]<<" ";
return 0;
}