#include <utility>
#include <functional>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
#define N 50001
vector<pair<int,int> > g[N];//vecinul, costul
int v[N];//0 nevizitat,1 vizitat,2 vizitat si optim
int d[N];
struct Compare
{	bool operator()(const int& a, const int& b)
	{	return d[a]>d[b];	
	}
};

int main ()
{	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	int i,j,n,m,a,b,c,mv,iv,ic,s;
	fin>>n>>m;
	for (i=1;i<=m;i++)
	{	fin>>a>>b>>c;
		g[a].push_back(make_pair(b,c));
	}
	vector<int> h;
	d[1]=0;
	v[1]=2;
	for (i=0;i<g[1].size();i++)
	{	iv=g[1][i].first;	
		ic=g[1][i].second;
		h.push_back(iv);
		v[iv]=1;
		d[iv]=ic;	
	}
	make_heap(h.begin(),h.end(),Compare());
	int flag;
	for(i=1;i<n;i++)
	{/*	for(j=0;j<h.size();j++)
		{	printf("%d ",h[j]);
		}
		printf("\n");	*/
		flag=false;
		mv=h[0];
		v[mv]=2;
		pop_heap(h.begin(),h.end(),Compare());
		h.pop_back();
		for (j=0;j<g[mv].size();j++)
		{	iv=g[mv][j].first;
			ic=g[mv][j].second;
			s=d[mv]+ic;
			if(v[iv]==2)continue;
			if(v[iv])
			{	if(d[iv]>s)
				{	d[iv]=s;
					flag=true;
				}
			}
			else
			{	d[iv]=s;
				v[iv]=1;
				h.push_back(iv);
				if(!flag)
				push_heap(h.begin(),h.end(),Compare());
			}	
		}
		if(flag)
		{	make_heap(h.begin(),h.end(),Compare());
		}
		if(h.size()==0)
		{break;}
	}
	for (i=2;i<=n;i++)
	{	fout<<d[i]<<" ";
	}
	return 0;	
}