#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 {
	unsigned short node;
	int cost;
	Node ( unsigned short 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 <unsigned short, std::vector <unsigned short>, 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() ) {

		while ( viz[q.top()] == 1 )
			q.pop();
		if ( !q.empty() ) {
			int p = q.top();
			q.pop();
			viz[p] = 1;

			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;
					q.push ( newNode );
				}
			}
		}
	}

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