#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define NMax 50010
#define inf (1 << 30) - 1

int n, m;
vector< pair<int, int> > G[NMax];
int d[NMax];

struct Cmp{
	bool operator()(int a, int b){
		return d[a] > d[b];
	}
};
priority_queue<int, vector<int>, Cmp> q;

void init();
void dijkstra();
void afisare();

int main(){
	init();
	dijkstra();
	afisare();
}

void init(){
	int i, x, y, c;
	fin >> n >> m;
	for(i = 1; i <= m; i++){
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
	for(i = 2; i <= n; i++)
		d[i] = inf;
}

void dijkstra(){
	int i, j, x;
	q.push(1);
	for(i = 0; i < n - 1; i++){
		x = q.top(); q.pop();
		for(j = 0; j < G[x].size(); j++)
			if(d[G[x][j].first] > d[x] + G[x][j].second){
				d[G[x][j].first] = d[x] + G[x][j].second;
				q.push(G[x][j].first);
			}
	}
}

void afisare(){
	for(int i = 2; i <= n; i++)
		fout << (d[i] == inf ? 0 : d[i]) << ' ';
}