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

#define NMAX 50000
#define INF 1e9

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

struct Node {
	int node, cost;
	Node ( int x, int c ) {
		node = x;
		cost = c;
	}
};

int dist[1 + NMAX];
std::vector < Node* > edges[1 + NMAX];
bool viz[1 + NMAX];

class CMP {
	public : bool operator () ( int a, int b ) {
		return dist[a] > dist[b];
	}
};

std::priority_queue <int, std::vector <int>, CMP > q;

int main() {

	int N, M;

	fin >> N >> M;

	for ( int i = 1; i <= M; ++i ) {
		int x, y, c;
		fin >> x >> y >> c;
		Node* node = new Node ( y, c );
		edges[x].push_back ( node );
	}

	for ( int i = 1; i <= N; ++i )
		dist[i] = INF;

	q.push ( 1 );
	viz[1] = true;
	dist[1] = 0;

	while ( !q.empty() ) {
		int p = q.top();
		q.pop();

		for ( int i = 0; i < edges[p].size(); ++i ) {
			int newNode = edges[p][i] -> node;
			if ( dist[p] + edges[p][i] -> cost < dist[newNode] ) {
				dist[newNode] = dist[p] + edges[p][i] -> cost;
	//			if ( !viz[newNode] ) {
					q.push ( newNode );
					viz[newNode] = 1;
	//			}
			}
		}
	}

	for ( int i = 2; i <= N; ++i ) {
		if ( dist[i] == INF )
			fout << "0 ";
		else
			fout << dist[i] << ' ';	
	}
 
	return 0;
}