#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define Nmax 50010
#define INF (1 << 30)

int n, m;
int C[Nmax], viz[Nmax];
void citire ();
vector < pair <int, int> > V[Nmax];
queue <int> Q;

void bellmanford () {
	
	int nod, fiu, i, cst;
	for (i = 2; i <= n; i++)
		C[i] = INF;
	
	Q.push (1); viz[1] = 1;
	while (!Q.empty()) {
		nod = Q.front ();
		
		for (i = 0; i < (int)V[nod].size (); i++) {
			fiu = V[nod][i].first; cst = C[nod] + V[nod][i].second;
			if (cst < C[fiu]) {
				C[fiu] = cst;
				if (!viz[fiu]) {
					Q.push (fiu);
					viz[fiu] = 1;
				} 
			}
		}
		
		Q.pop ();
	}
}

int main () {

	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);

	citire ();
	bellmanford ();
	
	for (int i = 2; i <= n; i++)
		printf ("%d ", C[i]);
	
	return 0;
}

void citire () {

	int a, b, c;
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf ("%d %d %d", &a, &b, &c);
		V[a].push_back ( make_pair (b, c) );
	}
}