#include <stdio.h>
#include <vector>
#include <queue>
#include <climits>

#define INF INT_MAX

using namespace std;

class prioritize{
		public: 
			bool operator ()(pair<int, int>&p1 ,pair<int, int>&p2){
				return p1.second>p2.second;
				}
};

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	int V, E;
	scanf("%d %d ", &V, &E);
	vector<vector<pair<int,int> > > neigh(V + 1);
	priority_queue<pair<int,int>, vector<pair<int,int> >, prioritize> pq;
	vector<bool> visited(V + 1, false);
	vector<int> dist;
	
	for(int i = 0; i < E; i++){
		int x, y, c;
		scanf("%d %d %d ", &x, &y, &c);
		neigh[x].push_back(make_pair(y,c));
	}
	
	for(int i = 0; i <= V; i++)
		dist.push_back(INF);
	
	visited[0] = true;
	dist[1] = 0;
	pq.push(make_pair(1,dist[1]));
	while(!pq.empty()){
		pair<int,int> current = pq.top();
		pq.pop();
		if(visited[current.first])
			continue;
		visited[current.first] = true;
		for(int i = 0; i < neigh[current.first].size(); i++)
			if((!visited[neigh[current.first][i].first]) && ( current.second + neigh[current.first][i].second < dist[neigh[current.first][i].first])){
				 dist[neigh[current.first][i].first] = current.second + neigh[current.first][i].second;
				 pq.push(make_pair(neigh[current.first][i].first, dist[neigh[current.first][i].first]));
			}
	}
	
	for(int i = 2; i <= V; i++)
		dist[i]!=INF ? printf("%d ", dist[i]) : printf("-1 ");
	
	return 0;
}