#include<fstream>
using namespace std;
#include<vector>
#define inf 100000
long n, m;

int main(){

	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	
	fin >> n >> m;
	vector<long> a(m+1,0), b(m+1, 0), c(m+1,0);
	vector<long> drum(n+1, inf);
	for(int i=1; i<=m; i++){
		fin >> a[i] >> b[i] >> c[i];
		if(a[i] == 1){
			drum[b[i]] = c[i];
		}
	}
	
	
	bool ok;
	do{
		
		ok = false;
		for(int i=1; i<=m; i++){
			if(drum[b[i]] > drum[a[i]] + c[i])
				drum[b[i]] = drum[a[i]] + c[i], ok=true;
		}
	
	
	}while(ok);
	
		
	for(int i=2; i<=n; i++){
		if(drum[i] == inf) fout << "0 ";
		else fout<< drum[i] << " ";
	}

	return 0;
}