#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int ma=10000;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,i,j,x,y,z,d[50001],s[50001],k,k1,k2,k3,v[50001],i1;
vector<vector<int> > a,b;
multimap<int, int> p;

void dijkstra(int start)
{
	p.insert(pair<int, int>(start,0));
	d[start]=0;
	for(i=2;i<=n;i++)
		d[i]=ma;
	while(k<n)
	{
		s[++k]=p.begin()->first;
		p.erase(s[k]);		
		if(!a[s[k]].empty())
			for(j=1;j<=a[s[k]].size();++j)
				if(d[a[s[k]][j-1]]>d[s[k]]+b[s[k]][j-1])
					{
						d[a[s[k]][j-1]]=d[s[k]]+b[s[k]][j-1];
						p.insert(pair<int, int>(a[s[k]][j-1],d[a[s[k]][j-1]]));
					}
	}
}
				
int main ()
{
	in>>n>>m;
	a.resize(50001);
	b.resize(50001);
	for(i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		a[x].push_back(y);
		b[x].push_back(z);
	}
dijkstra(1);
for(i=2;i<=n;i++)
	out<<d[i]<<" ";
return 0;
}