#include <cstdio>
#include <queue>
#include <vector>
#include <bitset>

#define f first
#define s second
#define inf 0x3f3f3f
#define maxn 50010

using namespace std;

int d[maxn], n, m;
struct cmp
{
	bool operator () (const int &a, const int &b) {
		return d[a] > d[b];
	}
};

priority_queue <int, vector <int>, cmp> Q;
vector <pair <int, int> > G[maxn];

void dijkstra ()
{
	
	bitset <maxn> viz;
	viz.reset ();
	
	int nod;
	for (int i = 2; i <= n; i++)
		d[i] = inf;

	d[1] = 0;
	
	Q.push (1);
	
	while (!Q.empty ()) {
		
		nod = Q.top ();
		Q.pop ();
		
		viz[nod] = 0;
		for (vector <pair <int, int> > :: iterator it = G[nod].begin (); it != G[nod].end (); it++) { 
			if (d[it -> f] > d[nod] + it -> s) {
				d[it -> f] = d[nod] + it -> s;
				if (viz[it -> f] == 0) {
					viz[it -> f] = 1;
					Q.push (it -> f);
				}
			}

		}
	}
	for (int i = 2; i <= n; i++)
			printf ("%d ", d[i] != inf ? d[i] : 0);
}
int main ()
{
	
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	int x, y, c;
	scanf ("%d%d\n", &n, &m);
	
	for (; m--; ) {
		scanf ("%d%d%d\n", &x, &y, &c);
		G[x].push_back (make_pair (y, c));
	}
	
	dijkstra ();
	
	return 0;
}