#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#define MAXN 50005
#define  pb push_back
#define INF 1000000000 
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int N,M,d[MAXN];
int a,b,c;
vector <int> G[MAXN],C[MAXN]; 
queue<int> q;
int main() {
	int i,j,x;
   cin>>N>>M;
    for(i=1;i<=M;i++)  {
	          cin>>a>>b>>c;
			  G[a].pb(b);
			  C[a].pb(c); }
	for(i=1;i<=N;i++)
	             d[i]=INF;
	d[1]=0;			 		  
    for(i=1;i<=N;i++) {
       q.push(1);
       while( q.size()>0) {
                   x=q.front();
                   q.pop();
                   for(j=0;j<G[x].size();j++)
                       if(d[x]+C[x][j]<d[G[x][j]]) {
                                  d[G[x][j]]=d[x]+C[x][j];
                                  q.push(G[x][j]); }
      }//end while
    } //end for 
	for(i=2;i<=N;i++)
	       cout<<d[i]<<" ";                                                                  
	return 0;
}