#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<fstream>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
using namespace std;

#define DMAX 501
#define INF 1 << 30

FILE *f, *g;
int n, m, s;

struct Graf{
	int d[DMAX];
	vector<int> Adj[DMAX], W[DMAX];
} G;
struct Heap{
	int size;
	int * d[DMAX], ind[DMAX];
} Q;

void MinHeapify(int i){
	int smalest = i;
	if ((2 * i) <= Q.size && *(Q.d[i]) > *(Q.d[2 * i]))
		smalest = 2 * i;
	if ((2 * i + 1) <= Q.size && *Q.d[smalest] > *Q.d[2 * i + 1]){
		smalest = 2 * i + 1;
	}

	if (smalest != i){
		swap(Q.d[i], Q.d[smalest]);
		swap(Q.ind[i], Q.ind[smalest]);
		MinHeapify(smalest);
	}
}
void PopMin(){
	swap(Q.d[1], Q.d[Q.size]);
	swap(Q.ind[1], Q.ind[Q.size]);
	Q.size--;
}

void Relax(int u, int v, int w){
	if (G.d[v] > G.d[u] + w){
		G.d[v] = G.d[u] + w;
	}
}
void Djikstra(){
	int i, next, lg, root;

	Q.size = n;
	for (i = 1; i <= n; i++)	G.d[i] = INF, Q.d[i] = &G.d[i], Q.ind[i] = i; 

	G.d[1] = 0;
	while (Q.size){
		root = Q.ind[1];
		lg = G.Adj[root].size();
		for (i = 0; i < lg; i++)	Relax(root, G.Adj[root][i], G.W[root][i]);
		PopMin();	
		MinHeapify(1);	
	}
}

int main(){
	int i, x, y, w;

	f = freopen("dijkstra.in", "r", stdin);
	g = freopen("dijkstra.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++){
		scanf("%d %d %d", &x, &y, &w);
		G.Adj[x].push_back(y);
		G.W[x].push_back(w);
	}

	Djikstra();

	for (i = 2; i <= n; i++) printf("%d ", G.d[i] == INF ? 0 : G.d[i]);

	return 0;
}