#include <fstream>
#include <set>
#include <vector>
#include <utility>
#define mp make_pair
#define MAXN 50010
#define INF 1000000000
using namespace std;
set<pair<int,int> > myset;
vector<pair<int,int> >v[MAXN];
int x,y,c,m,n,i,d[MAXN],used[MAXN];
int main()
{
	ifstream fi("dijkstra.in");
	ofstream fo("dijkstra.out");
	fi>>n>>m;
	for(i=1;i<=m;i++)
	{
		fi>>x>>y>>c;
		v[x].push_back(make_pair(y,c));
	}
	for(i=2;i<=n;i++) d[i]=INF; 
	myset.insert(mp(0,1));
	while(!myset.empty())
	{
		while(!myset.empty() and used[(*myset.begin()).second]) 
			myset.erase(myset.begin());
		if(myset.empty()) break;
		x=(*myset.begin()).second; used[x]=1;
		myset.erase(myset.begin());
		for(i=0;i<v[x].size();i++)
		if(d[v[x][i].first]>d[x]+v[x][i].second)
		{
			d[v[x][i].first]=d[x]+v[x][i].second;
			myset.insert(mp(d[v[x][i].first],v[x][i].first));
		}
	}
	for(i=2;i<=n;i++) if(d[i]<INF) fo<<d[i]<<" "; else fo<<"0 ";
	fo<<"\n";
	return 0;
}