// Dijkstra's shorthest path algorithm
// Code by Cristian "Dr.Optix" Dinu <[email protected]>

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

using namespace std;

#define INF 0xfffffff

struct Edge {
	int y, cost;
};

int nodes, edges, dist[50001];
vector<Edge> graph[50001];
queue<int> q;

FILE* fin = fopen("dijkstra.in","r");
FILE* fout = fopen("dijkstra.out","w");

int main(int argc, char** argv) {
	int x, y, cost;
	Edge e;
	
	// Read data
	fscanf(fin, "%d %d", &nodes, &edges);
	for (int i = 1; i <= edges; ++i) {
		fscanf(fin, "%d %d %d", &x, &e.y, &e.cost);
		graph[x].push_back(e);
	}
	
	// Output the graph
	/*for (int i = 1; i <= nodes; ++i) {
		printf("%d: ", i);
		for (int j=0; j < graph[i].size(); ++j) {
			printf("%d, ", graph[i][j].y);
		}
		printf("\n");
	}*/
	
	// Dijkstra
	dist[1] = 0;
	for (int i = 2; i <= nodes; ++i) {
		dist[i] = INF;
	}
	q.push(1);
	
	while (!q.empty()) {
		x = q.front();
		
		for (int i = 0; i < graph[x].size(); ++i) {
			y = graph[x][i].y;
			cost = graph[x][i].cost;
			
			if (dist[y] > dist[x] + cost) {
				dist[y] = dist[x] + cost;
				q.push(y);
			}
		}
		
		q.pop();
	}
	
	// Write the output
	for (int i = 2; i <= nodes; ++i) {
		if (dist[i] != INF) {
			fprintf(fout, "%d ", dist[i]);
		} else {
			fprintf(fout, "0 ");
		}
	}
}