#include<fstream>
#include<algorithm>
#include<vector>
#include<set>
#define inf 1000000000
using namespace std;
int n,m,i,x,y,ct,d[50003];
vector<int>v[50003],c[50003];
set< pair<int,int> > hp;
void djikstra()
{int i,minn,nd;
	for(i=2;i<=n;i++)d[i]=inf;
	hp.insert(make_pair(0,1));
	while(hp.size()>0)//cat timp mai am noduri nemarcate
	{
		minn=(*hp.begin()).first; nd=(*hp.begin()).second;
		hp.erase(*hp.begin());
		for(i=0;i<v[nd].size();i++)
			if(d[v[nd][i]] > minn + c[nd][i])
			{
			   d[v[nd][i]] = minn + c[nd][i];
				hp.insert(make_pair(d[v[nd][i]],v[nd][i]));
			}
	}
}
int main()
{
	ifstream f("dijkstra.in");ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>ct;
		v[x].push_back(y);
		c[x].push_back(ct);
	}
	djikstra();
	for(i=2;i<=n;i++)
		if(d[i]!=inf)g<<d[i]<<" ";else g<<0<<" ";
	f.close();g.close();
return 0;}