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

void dijkstra(int start)
{
	p.insert(make_pair(0,start));
	d[start]=0;
	for(i=2;i<=n;i++)
		{
			d[i]=ma;
			
		}
	while(k<n)
	{
		s[++k]=(*p.begin()).second;
		
		p.erase(*(p.begin()));		
		
		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(make_pair(d[a[s[k]][j-1]],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++)
	{
		if(d[i]!=ma)
		out<<d[i]<<" ";
	else
		out<<"0 ";
	}
return 0;
}