#include <cstdio>
#include <vector>
#include <fstream>
#include <set>
#include <climits>

using namespace std;

struct nod{
	int varf;
	int cost;
	};

vector<nod>  v[50005];
set< pair < int , int > > s;

int main ()
{

    int n,m;
	ifstream in ("dijkstra.in");
	freopen ("dijkstra.out","w",stdout);
	in>>n>>m;
	for(;m;--m){
		nod x;
		int i;
		in>>i>>x.varf>>x.cost;
		v[i].push_back(x);
		}
	vector<int> d(n+1,INT_MAX);
	s.insert(make_pair(0,1));
	while(s.size()>0){
		int val=(*s.begin()).first, x=(*s.begin()).second;
		s.erase(*s.begin());
		for(vector<nod>::iterator it=v[x].begin();it<v[x].end();++it)
			if(d[(*it).varf]>val+(*it).cost){
				d[(*it).varf]=val+(*it).cost;
				s.insert(make_pair(d[(*it).varf],(*it).varf));
				}
		}
	for(int i=2;i<=n;++i)
	printf("%d ",d[i]==(INT_MAX)?0:d[i]);

	return 0;}