#include<cstdio>
#include<vector>
#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()
{
	int nod;
	int i , j;
	for ( i = 1 ; i <= n ; ++i ) 
		d[i] = inf;
	
	Q.push(1);
	in[1] = true;
	d[1] = 0;
	
	while ( ! Q.empty() ) {
		nod = Q.front() , Q.pop();
		in[nod] = false;
		
		for ( i = 0 ; i < G[nod].size() ; ++i )
			if ( d[nod] + G[nod][i].s < d[G[nod][i].f] ) {
				d[G[nod][i].f] = d[nod] + G[nod][i].s;
				if ( in[G[nod][i].f] == false ) Q.push(G[nod][i].f);
				in[G[nod][i].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;
}