#include<fstream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 2000000000
vector <int> A[50001];
vector <int> C[50001];
queue <int> Q;
int d[50001], viz[50001];
int main(){
	int n, m, i, j, x,y,c, k, ok = 1, min;
	f >> n >> m;
	for( i = 1; i <= m; i++ )
	{
		f >> x >> y >> c;
		A[x].push_back(y);
		C[x].push_back(c);
	}
	for(i = 1; i <= n; i++)
		d[i] = inf;
	d[1] = 0;
	while( ok == 1){
		min = inf;
		for(i = 1; i <= n; i++)
			if(min > d[i] && viz[i] == 0 ){
				min = d[i];
				k = i;
			}
		if( min != inf){
			viz[k] = 1;
			for(i = 0; i < A[k].size(); i++)
				if(d[A[k][i]] > d[k] + C[k][i] )
					d[A[k][i]] = d[k] + C[k][i];
		}
		else ok = 0;
	}
	for( i = 2; i <= n; i++)
		if( d[i] != inf)
			g << d[i] << " ";
		else
			g << "0 ";
	return 0;
}