#include <fstream>
#include <set>
#include <vector>
#include <utility>
#define MAXN 50010
using namespace std;
set<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<=n;i++)
	{
		fi>>x>>y>>c;
		v[x].push_back(make_pair(y,c));
	}
	for(i=2;i<=n;i++) d[i]=int(2e9); 
	myset.insert(1);
	while(!myset.empty())
	{
		while(!myset.empty() and used[*myset.begin()]) myset.erase(myset.begin());
		if(myset.empty()) break;
		x=*myset.begin(); 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(v[x][i].first);
		}
	}
	for(i=2;i<=n;i++) if(d[i]<int(2e9)) fo<<d[i]<<" "; else fo<<"0 ";
	fo<<"\n";
	return 0;
}