#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;

const char in[]="dijkstra.in";
const char out[]="dijkstra.out";

const int N = 50005;

vector< pair<int, int> >G[N];
bitset<N>in_Q;
queue<int>Q;
int n, m, d[N], x, y, c;

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		
		scanf("%d %d", &n, &m);
		
		for(int i = 1 ; i <= n ; ++i)d[i] = -1;
		
		for(int i = 1 ; i <= m ; ++i)
		{
			scanf("%d %d %d", &x, &y, &c);
			
			G[x].push_back(make_pair(y, c));
		}
		
		in_Q[1] = true; 
		Q.push(1);
		d[1] = 0;
		
		while(Q.size())
		{
			x = Q.front();
			Q.pop();
			in_Q[x] = false;
			
			for(vector< pair<int, int> >::iterator it = G[x].begin(); it != G[x].end() ; ++it)
				if(d[x] + it->second <= d[it->first] || d[it->first] == -1)
				{
					d[it->first] = d[x] + it->second;
					Q.push(it->first);
					in_Q[it->first] = true;
				}
				
		}
		for(int i = 2 ; i <= n ; ++i)
			if(d[i] == -1)printf("0 ");
			else printf("%d ", d[i]);
				
		return 0;
}