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

#define inf 0xfffffff

using namespace std;

struct nod
{
	int inc, sf, cost;
	nod(int Inc, int Sf, int Cs)
	{
		inc = Inc;
		sf = Sf;
		cost = Cs;
	}
};

vector <nod> v[50001];
deque <int> coada;
int n, m, dist[50001];

int start, end, cost, i;

void dijkstra()
{	
	dist[1]=0;
	coada.push_back(1);
	for(i = 2;i <= n;dist[i++] = inf);	
	
	while(!coada.empty()){
		start = coada.front();
		
		if(dist[start] != inf)
			for(i = 0;i < (signed)v[start].size();i++)
			{
				end = v[start][i].sf;
				cost = v[start][i].cost;
				
				if(dist[end] > dist[start] + cost){
					dist[end] = dist[start] + cost;
					coada.push_back(end);
				}
			}
			
		coada.pop_front();
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for(i = 0;i < m;i++)
	{
		scanf("%d %d %d", &start, &end, &cost);
		v[start].push_back(nod(start, end, cost));
	}
	
	dijkstra();
	
	for(i = 2;i <= n;i++)
		if(dist[i] != inf)
			printf("%d ", dist[i]);
		else
			printf("0 ");
}