#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

const long MAX = 50010;
const long inf = 0x3f3f3f3f;

vector< pair<long,long> > G[MAX];
long n,m;
long D[MAX]; 
bool U[MAX];
long x;


struct comp {
	int operator()(long x, long y) { return D[x]>D[y] ? 1 : 0; }
};

priority_queue< long, vector<long>, comp > Q;
void relaxeaza(pair<long, long> p) { 
	if ( D[p.first] <= D[x]+p.second ) 
		return;
	D[p.first] = D[x] + p.second;
	if ( !U[p.first] ) Q.push(p.first), U[p.first] = true;
}

void dijkstra() {
	memset(U, 0, sizeof(U));
	memset(D, 0x3f, sizeof(D));
	D[1] = 0; U[1] = true;
	Q.push(1);
	while ( !Q.empty() ) {
		x = Q.top(); Q.pop();
//		U[x] = true;
		for_each(G[x].begin(), G[x].end(), relaxeaza);
		U[x] = false;
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	scanf("%ld %ld", &n, &m);
	for (long i=0; i<m; ++i) {
		long x,y,c;
		scanf("%ld %ld %ld", &x, &y, &c);
		G[x].push_back(make_pair(y,c));
	}

	dijkstra();

	freopen("dijkstra.out", "w", stdout);
	for (long i=2; i<=n; ++i)
		printf("%ld ", D[i]<inf ? D[i] : 0);
	printf("\n");
	return 0;
}