#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define maxn 50005
#define inf 1000000000
using namespace std;

vector < pair <int , int> > G[maxn];
queue <int> Q;
int i , j ,  d[maxn] , n , m , a , b, c , x;
//bool in[maxn];

void Bellman_Ford()
{
    bitset<maxn> in;
    for ( i = 1 ; i <= n ; ++i ) d[i] = inf , in[i] = 0;
	int nod;
	int i , j;
	Q.push(1);
	in[1] = true;
	d[1] = 0;
	
	while ( ! Q.empty() ) {
		nod = Q.front() , Q.pop();
		in[nod] = false;
		
		for ( vector < pair <int ,int > > :: iterator it = G[nod].begin() ; it != G[nod].end()  ; ++it )
			if ( d[nod] + it -> s < d[it -> f] ) {
				d[it -> f] = d[nod] + it -> s;
				if ( in[it -> f] == false ) Q.push(it -> f);
				in[it -> f] = true;
			}
	}
	
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	for (scanf("%d %d",&n,&m); m -- ; ) {
		scanf("%d %d %d",&a,&b,&c);
		G[a].pb(mp(b , c));
		//G[b].pb(mp(a , c));
	}
	
	Bellman_Ford();
	
	for ( i = 2 ; i <= n ; ++i ) {
        if ( d[i] != inf ) 
	    printf("%d ",d[i]);
	    else
	    printf("0 ");
     }
	/*
	for ( ; x -- ; ) {
		scanf("%d %d",&a,&b);
		printf("%d\n",d[a] + d[b]);
	}
	*/
	
return 0;
}