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


bool cmp( int a, int b ) {
     return a > b;
   }

int main()
{
	ifstream fin("dijkstra.in");
	freopen("dijkstra.out","w",stdout);
	int n,m,x,y,c,d[50001];
	vector<int> muchii[50001];
	vector<int> costuri[50001];
	//multiset< pair <int,int> > h;
	vector<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(y);
		costuri[x].push_back(c);
		if(x==1) 
		{
				d[y]=c;
				//h.insert(make_pair(c,y));
				h.push_back(make_pair(c,y));
		}
				
	}
	make_heap(h.begin(),h.end());
	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];
			int costvecin = costuri[nod][i];
			if(d[vecin]>costnod+costvecin) 
				{
					d[vecin]=costnod+costvecin;
					//h.insert(make_pair(d[vecin],vecin));
					h.push_back(make_pair(d[vecin],vecin));
					push_heap(h.begin(),h.end());
				}
		}
	}
	for(int i=2; i<=n; ++i)
		if(d[i]!=inf)
			printf("%d ",d[i]);
		else printf("0 ");
			
	return 0;
}