#include<fstream.h>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 10000000

using namespace std;

vector< pair<int, int> > l[50001];
 queue<int> c;
int n,m,d[50001];
bool inq[50001];
void initial()
{ for(int i=1;i<=n;i++)
	{ d[i]=INF;
      inq[i]=0;
	}
d[1]=0;
}
void relaxare(int u,int p,int w)
{ if(d[p]>d[u]+w)
   { d[p]=d[u]+w;
     if(inq[p]==0)
	       { c.push(p);
	         inq[p]=1;
	       }
   }
}
void rezolvare()
{ initial();
  c.push(1);
  while(!c.empty())
  { int a=c.front();
    c.pop();
	inq[a]=0;
	for(vector<pair<int,int> > ::iterator it=l[a].begin();it!=l[a].end();it++)
	   relaxare(a,it->first,it->second);
  }
	
}
int main()
{  ifstream f("dijkstra.in");
   ofstream g("dijkstra.out");
 f>>n>>m;
   for(int i=1;i<=m;i++)
	 { int x,y,z;
		f>>x>>y>>z;
        l[x].push_back(make_pair(y,z));
	 }
	rezolvare();
for(int i=2;i<=n;i++)
 if(d[i]==INF) 
	 g<<0<<" ";
 else	 
	 g<<d[i]<<" ";	
	return 0; }