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

#define NMAX 50001
#define INF 123456789
using namespace std;

vector<pair<int, int> > adList[NMAX];
queue<pair<int, int> > Q;
int distances[NMAX], visited[NMAX];
int N, M;

void dijkstra(){

	while(!Q.empty()){
		pair<int, int> node = Q.front();
		Q.pop();
		visited[node.first] = 0;

		for(int i = 0; i < adList[node.first].size(); i++){
			pair<int, int> neigh = adList[node.first][i];
			if(distances[neigh.first] > distances[node.first] + neigh.second){
				distances[neigh.first] = distances[node.first] + neigh.second;
				if(visited[neigh.first] == 0){
					Q.push(make_pair(neigh.first, distances[neigh.first]));
					visited[neigh.first] = 1;
				}
			}
		}
	}
}

int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	int a, b, c;
	f >> N >> M;
	for(int i = 0; i < M; i++){
		f >> a >> b >> c;
		adList[a].push_back(make_pair(b, c));
	}

	f.close();

	for(int i = 1; i<= NMAX; i++)
		distances[i] = INF;
	distances[1] = 0;
	visited[1] = 1;
	Q.push(make_pair(1, 0));
	dijkstra();

	for(int i = 2; i <= N; i++)
		g << distances[i] << " ";

	g.close();
	return 0;
}