#include<stdio.h>
#include<stdlib.h>

#include <cstring>
#include <algorithm>
#include<vector>
#include<set>
#include <fstream>

using namespace std;

int INF=0x3f3f3f3f;

int M,N;

vector<pair<int,int>> L[50000];
int D[50000];

set<pair<int,int>> Q;

void dijkstra(){
	memset(D, INF , N*sizeof(int));
	D[0]=0; 
	
	Q.insert(make_pair(D[0],0));

	int u;
	set<pair<int,int>>::iterator itset;
	vector<pair<int,int>>::iterator itvec; 

	while(!Q.empty()){
		itset = Q.begin();
		u=(*itset).second;	
		Q.erase(itset);

		int cost,vecin;

		for (itvec = L[u].begin(); itvec != L[u].end(); ++itvec) {
			vecin=(*itvec).first;
			cost=(*itvec).second;
			
			if((D[u] + cost) < D[vecin]){
				D[vecin]=D[u]+cost;
				Q.insert(make_pair(D[vecin],vecin));
			}
		}
	}		
}

int main(){
	
	ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
	//freopen("dijkstra.in","rt",stdin);
	//freopen("dijkstra.out","wt",stdout);
	
	fin >> N >> M;
	//scanf("%d %d",&N,&M);

	int x,y,cost;

	for(int i=0;i<M;i++){
		fin >> x >> y >> cost;
		//scanf("%d %d %d",&x,&y,&cost);
		L[x-1].push_back(make_pair(y-1,cost));	
	}

	dijkstra();

	for(int i=1;i<N;i++){
		if(D[i]==INF)
			D[i]=0;
		//printf("%d ",D[i]);
		 fout << D[i] << " ";
	}

	fin.close();
    fout.close();

	return 0;
}