#include <algorithm>
#include <vector>
#include <fstream>
#include <utility>
#define N 65536
using namespace std;
bool v[N];
int l[N];
vector<pair<int,int> >h;  
vector<pair<int,int> > g[N];
struct Compare
{	bool operator()(const pair<int,int>& a,const pair<int,int>& b)
	{	return 	a.second>b.second;
	}
};

int main ()
{	
	int n,m,a,b,c;
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin>>n>>m;
	for (int i=1;i<=m;i++)
	{	fin>>a>>b>>c;
		g[a].push_back(make_pair(b,c));
	}
	h.push_back(make_pair(1,0));
	while(h.size()>0)
	{	pair<int,int> p=h[0];
		pop_heap(h.begin(),h.end(),Compare());
		h.pop_back();
		if(!v[p.first])
		{	v[p.first]=true;
			l[p.first]=p.second;
			for (vector<pair<int,int> >::iterator i=g[p.first].begin();i!=g[p.first].end();++i)
			{	h.push_back(make_pair(i->first,i->second+p.second));					
				push_heap(h.begin(),h.end(),Compare());
			}
		}
	}
	for (int i=2;i<=n;i++)
	{	printf("%d ",l[i]);
	}	
	return 0;
}