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

#define VISITED 1
#define NEW 0
using namespace std;

typedef struct vertex {
	int dest_id;
	int cost;
} Edge;

typedef struct {
	int n;
	vector < vector <Edge> > V;
} Graph;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
Graph G;
queue <int> ord;

void read () {
	int m;
	in >> G.n >> m;
	
	for (int i = 0; i <= G.n; ++i) {		 
		vector <Edge> v;
		G.V.push_back(v);
	}
	
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		in >> x >> y >> z;
		
		Edge e = {y, z};
		
		G.V[x].push_back(e);
	}
}

int *dijkstra () {
	int *dist = new int[G.n+1];
	int *visited = new int[G.n+1]();
	
	for (int i = 1; i <= G.n; ++i) {
		dist[i] = -1;
	}
	
	for (unsigned int i = 0; i < G.V[1].size(); ++i) {
		ord.push(G.V[1][i].dest_id);
		dist[G.V[1][i].dest_id] = G.V[1][i].cost;
	}
	
	while (!ord.empty()) {
		int curr_id = ord.front();
		
		for (unsigned int i = 0; i < G.V[curr_id].size(); ++i) {			
			int test = dist[curr_id] + G.V[curr_id][i].cost;
			
			if (dist[G.V[curr_id][i].dest_id] == -1 || test < dist[G.V[curr_id][i].dest_id]) {
				dist[G.V[curr_id][i].dest_id] = test;
				visited[G.V[curr_id][i].dest_id] = NEW;
			}
			
			if (visited[G.V[curr_id][i].dest_id] == NEW) {
				ord.push(G.V[curr_id][i].dest_id);
			}
		}
		
		visited[curr_id] = VISITED;
		ord.pop();
	}
	
	delete[] visited;
	
	return dist;
}
	
		  
	
int main (void) {
	
	read();
	int *dist = dijkstra();
	
	for (int i = 2; i <= G.n; ++i) {
		out << dist[i] << " ";
	}
	
	return 0;
}