#include<cstdio>
#include<fstream>
#include<set>
#include<vector>
using namespace std;
#define inf 250000001

int main()
{
	ifstream fin("dijkstra.in");
	freopen("dijkstra.out","w",stdout);
	int n,m,x,y,c,d[50001];
	vector< pair<int,int> > muchii[50001];
	//vector<int> costuri[50001];
	multiset< pair <int,int> > h;
	
	fin>>n>>m;
	for(int i=1; i<=n; ++i)
		d[i]=inf;
	for(int i=1; i<=m; ++i)
	{
		fin>>x>>y>>c;
		muchii[x].push_back(make_pair(y,c));
		//costuri[x].push_back(c);
		if(x==1) 
		{
				d[y]=c;
				h.insert(make_pair(c,y));
		}
				
	}
	
	while(h.size())
	{
		int nod=(*h.begin()).second;
		int costnod=(*h.begin()).first;
		h.erase(*h.begin());
		for(unsigned int i=0; i<muchii[nod].size(); ++i)
		{
			int vecin = muchii[nod][i].first();
			int costvecin = muchii[nod][i].second();
			if(d[vecin]>costnod+costvecin) 
				{
					d[vecin]=costnod+costvecin;
					h.insert(make_pair(d[vecin],vecin));
				}
		}
	}
	for(int i=2; i<=n; ++i)
		if(d[i]!=inf)
			printf("%d ",d[i]);
		else printf("0 ");
			
	return 0;
}