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