#include<stdio.h>
	#include<vector>
	#define MAX 50001
	#define inf 50000001
	using namespace std;
	int n , m , h[MAX] , p[MAX]  , q , d[MAX] , x[MAX];
	vector<int> a[MAX] , c[MAX] ;
	vector<int>::iterator it , it1;
	
	void citire();
	void dijkstra();
	void tipar();
	void urcare( int n);
	void coborare( int n);
	void swap(int &x , int &y );
	
	int main()
	{
		citire();
		dijkstra();
		tipar();
		return 0;
	}
	
	void citire()
	{
		int x , y , cost ;
		freopen("dijkstra.in" , "r" , stdin );
		scanf("%d%d" , &n , &m );
		for( int i = 1 ; i<= m ; ++i )
		{
			scanf("%d%d%d" , &x , &y , &cost );
			a[x].push_back(y);
			c[x].push_back(cost);
		}
	}
	
	void dijkstra()
	{
		int u;
		for( int i = 1 ; i<= n ; ++i )
		{
			d[i] = inf;
			h[i] = inf;
			p[i] = i;
			x[i] = i;
		}
		q = n;
		d[1] = 0;
		h[1] = 0;
		while(q)
		{
			u = x[1] ;
			for(it = a[u].begin() , it1 = c[u].begin() ; it < a[u].end(); ++it , ++it1 )
				if(d[*it] > d[u] + *it1)
				{
					d[*it] = d[u] + *it1;
					h[p[*it]] = d[u] + *it1;
					coborare(p[*it]);
					urcare(p[*it]);
				}
			swap(h[q],h[1]);
			swap(p[x[q]],p[x[1]]);
			swap(x[q],x[1]);
			q--;
			coborare(1);
		}
	}
	
	void urcare(int n)
	{
		while(h[n] < h[n/2] && n/2 )
		{
			swap(p[x[n]],p[x[n/2]]);
			swap(x[n],x[n/2]);
			swap(h[n],h[n/2]);
			n/=2;
		}
	}
	
	void coborare(int n)
	{
		int min;
		while((h[n] > h[2*n] && 2*n <= q) || (h[n] > h[2*n+1] && 2*n+1 <= q))
		{
			min = n;
			if(h[2*n] < h[min])
				min = 2*n;
			if(h[2*n+1] < h[min])
				min = 2*n+1;
			if(min != n)
			{
				swap(p[x[n]],p[x[min]]);
				swap(x[n],x[min]);
				swap(h[n],h[min]);
				n = min;
			}
		}
	}
	
	void swap( int &x , int &y)
	{
		int aux = x; 
		 x = y ;
		 y = aux;
	}
	
	void tipar()
	{
		freopen("dijkstra.out" , "w", stdout );
		for( int i = 2 ; i<= n ; ++i )
			if(d[i] != inf )
				printf("%d " , d[i]);
			else
				printf("0 ");
	}