#include<stdio.h>
#include<vector>
#include<set>

using namespace std;

#define NMAX 50001
#define INF 50000000

int d[NMAX]  ,N , M;
vector<int> G[NMAX] , C[NMAX];
struct Compare{
	bool operator()(int a , int b) {
		return d[a] < d[b] ;
	}
};
multiset<int,Compare> Q;

void citire();
void dijkstra();
void tipar();

int main()
{
	citire();
	dijkstra();
	tipar();
	return 0;
}

void citire()
{
	int x , y , c;
	freopen("dijkstra.in" , "r" , stdin );
	scanf("%d%d" , &N , &M );
	for(int i = 1 ; i <= M ; ++i ){
		scanf("%d%d%d" , &x , &y , &c );
		G[x].push_back(y);
		C[x].push_back(c);
	}
}

void dijkstra()
{
	int nod;
	for(int i = 1 ; i <= N ; ++i )
		d[i] = INF ;
	d[1] = 0;
	Q.insert(1);
	while(!Q.empty()) {
		nod = *Q.begin();
		Q.erase(Q.begin());
		for(int i = 0 ; i < G[nod].size() ; ++i )
			if(d[nod] + C[nod][i] <= d[G[nod][i]]) {
				d[G[nod][i]] = d[nod] + C[nod][i];
				Q.insert(G[nod][i]);
			}
	}
}

void tipar()
{
	freopen("dijkstra.out" , "w"  , stdout );
	for(int i = 2 ; i <= N ; ++i )
		if(d[i] == INF)
			printf("0 ");
		else
			printf("%d " , d[i] );
	
}