#include<stdio.h>
	#include<fstream>
	#include<vector>
	#define MAX 50001
	#define inf 50000001
	using namespace std;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	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>>n>>m;
		for(int i = 1 ; i<= m ; ++i )
		{
			f>>x>>y>>cost;
			a[x].push_back(y) , c[x].push_back(cost);
		}
		f.close();
	}
	
	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;
			std::swap(h[n],h[n/2]);
			std::swap(p[n],p[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;
				std::swap(h[n],h[2*n+1]);
				std::swap(p[n],p[2*n+1]);
				n =2*n+1;
			}
			else
			{
				x[p[n]] = 2*n;
				x[p[2*n]] = n;
				std::swap(h[n],h[2*n]);
				std::swap(p[n],p[2*n]);
				n = 2*n;
			}
	}
	
	void tipar()
	{
		for( int i = 2 ; i<= n ; ++i )
			if(d[i]!=inf)
				g<<d[i]<<' ';
			else
				g<<"0 ";
		g.close();
	}