#include<iostream>
#include<fstream>
#include<set>
#include<vector>
#include<string.h>
#include<limits.h>

//are timp mai bun cu priority queue - vezi fmcm(Flux Maxim de Cost Minim)

using namespace std;

const int INF=0x3f3f3f3f;

struct node{
	int where;
	int cost;
	node(int _where, int _cost){
		where=_where;
		cost=_cost;
	}
};


int main(){
	FILE *in=fopen("dijkstra.in","r"), *out=fopen("dijkstra.out","w");
	int i, n, m, from, where, cost;
	set< pair<int,int> > s;
    fscanf(in,"%d %d",&n,&m);
	vector<node> graf[n+1]; vector<node>::iterator it;
	int dist[n+1];
	memset(dist, INF, sizeof dist); 
	dist[1]=0; s.insert(make_pair(0,1));
	for(i=1;i<=m;i++){
        fscanf(in,"%i %i %i", &from, &where, &cost);
        node *nd=new node(where, cost);
		graf[from].push_back(*nd);
	}
	
	while(!s.empty()){
		int sCost=s.begin()->first, sWhere=s.begin()->second; 
		s.erase(s.begin());
		for(it=graf[sWhere].begin(); it!=graf[sWhere].end(); it++){ 
			if( (*it).cost+sCost < dist[(*it).where]){
				if(dist[(*it).where]!=INF) s.erase(s.find(make_pair(dist[(*it).where],(*it).where)));
				dist[(*it).where]=sCost+(*it).cost;
				s.insert(make_pair(dist[(*it).where],(*it).where));
			}
		}
	}
	
	for(i=2;i<=n;i++){
		if(dist[i]==INF) fprintf(out,"0 ");
		else fprintf(out,"%i ",dist[i]);
	}
	
	
	fclose(in); fclose(out);
	return 0;
}