#include<fstream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
ifstream in("grader2.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;

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);
	}
	s[0]=1;
	v[1]=2;
	while(k<n-1)
	{
		k1=-1;
		k2=0;
		for(i1=0;i1<=k;i1++)
		{
			if(!b[s[i1]].empty())
			for(int it=0;it!=b[s[i1]].size();++it)
				if((b[s[i1]][it]<k1 || k1==-1) && !v[a[s[i1]][it]])
					{
					k1=b[s[i1]][it];
					k2=s[i1];
					k3=a[s[i1]][it];
					}
		}
		if(k1>=0)
		{s[++k]=k3;
		v[s[k]]=2;
		d[s[k]]=d[k2]+k1;
		}
		else
				k=n;
	}
	for(i=2;i<=n;i++)
		out<<d[i]<<" ";
}