#include <cstdio>
#include <queue>
#include <bitset>
#include <algorithm>
#define son first
#define cost second
using namespace std;

typedef pair <int, int> graph_node;
const int NMAX = 50002, INFI = 2e9;

int dist[NMAX], N;

struct predicate {

	inline bool operator () (const int &a, const int &b) {

		return dist[a] < dist[b];

	}

};

vector <graph_node> G[NMAX];
priority_queue <int, vector <int>, predicate> Q;

void dijkstra (const int &start_node) {

	int node, i;
	for (i = 1; i <= N; ++i)
		dist[i] = INFI;
	dist[start_node] = 0;
	Q.push (start_node);
	while (!Q.empty ()) {
		node = Q.top ();
		Q.pop ();
		for (vector <graph_node> :: iterator i = G[node].begin (); i != G[node].end (); ++i)
			if (i->cost + dist[node] < dist[i->son])  {
				dist[i->son] = i->cost + dist[node];
				Q.push (i->son);
			}

	}
	for (i = 2; i <= N; ++i)
		printf ("%d ", dist[i]);

}

int main () {

	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out" , "w", stdout);
	int M, a, b, c;
	scanf ("%d%d", &N, &M);
	while (M--) {
        scanf ("%d%d%d", &a, &b, &c);
        G[a].push_back (make_pair (b, c));
	}
	dijkstra (1);

}