#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
const int NMAX = 50003;
const int MMAX = 250003;
const int inf = 0x3f3f3f3f;

vector< pair<int,int> > G[NMAX];
int n; 
int d[NMAX];

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

void bellman_ford()
{
	d[1] = 0;
	for (int i = 2; i <= n; ++i)
		d[i] = inf;
	
	queue<int> Q;
	vector<bool> inQ(n+1,false);
	
	inQ[1] = true;
	Q.push(1);
		
	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();
		inQ[x] = false;
		
		vector< pair<int,int> >::iterator it;
		for (it = G[x].begin(); it != G[x].end(); ++it)
			if (d[it->first] > d[x] + it->second) {
				d[it->first] = d[x] + it->second;
				if (!inQ[it->first])
					Q.push(it->first);
					inQ[it->first] = true;
			}
	}
}

void print()
{
	freopen("dijkstra.out","w",stdout);
	for (int i = 2; i <= n; ++i)
		printf("%d ", d[i] == inf ? 0 : d[i]);
}

int main()
{
	read();
	bellman_ford();
	print();
	return 0;
}