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

#define f first
#define s second
#define inf 0x3f3f3f
#define maxn 50010
#define DIM2 8192
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];

char vec[DIM2];
int poz;
void cit(int &x)   
{   
  x=0;   
  while(vec[poz]<'0' || vec[poz]>'9')   
       if(++poz==DIM2) fread(vec,1,DIM2,stdin),poz=0;   
  
    while(vec[poz]>='0' && vec[poz]<='9')   
    {   
        x=x*10+vec[poz]-'0';   
        if(++poz==DIM2) fread(vec, 1, DIM2, stdin),poz=0;   
    }  
}   
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;
	cit (n); cit (m);
	
	for (; m--; ) {
		//scanf ("%d%d%d\n", &x, &y, &c);
		cit (x); cit (y); cit (c);
		G[x].push_back (make_pair (y, c));
	}
	
	dijkstra ();
	
	return 0;
}