#include<fstream>
#include<vector>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

const int INF = 123456789;
const int MAX_M = 250005;
const int MAX_N = 50004;

struct pereche{
    int nod;
	int dist;
};

vector < pair<int,int> > a[MAX_N];
int i,j,n,m,x,y,c;
int d[MAX_N];
int heap_size;
pereche h[MAX_N];

void down_heap(int k, const int &heap_size){
	 int son=1;
	 
	 while(son)
	    if(2*k<=heap_size){
	    	son=2*k;
	    	if(2*k+1<=heap_size && h[2*k+1].dist<h[2*k].dist) son=2*k+1;
	    	
	    	if(h[son].dist<h[k].dist){
	    		swap(h[k],h[son]);
	    		k=son;
			} else son=0;
		}else son=0;
}

void up_heap(int k, const int &heap_size){
	 while(k>1 && h[k/2].dist>h[k].dist){
	 	swap(h[k/2],h[k]);
	 	k/=2;
	 }
}

void insert_heap(int nod, int dist, int &heap_size){
	 ++heap_size;
	 h[heap_size].nod = nod;
	 h[heap_size].dist = dist;
	 up_heap(heap_size,heap_size);
}

void delete_heap(int &heap_size){
	 h[1]=h[heap_size--];
	 down_heap(1,heap_size);
}

int main(){
	fi>>n>>m;
	for(i=1;i<=m;i++){
		fi>>x>>y>>c;
		a[x].push_back(make_pair(y,c));
	}
		
	for(i=1;i<=n;i++) d[i]=INF;
	d[1]=0; heap_size=0;
	insert_heap(1,0,heap_size);
	
	while(heap_size>0){
		int nod = h[1].nod;  
		delete_heap(heap_size); 
		
		for(j=0;j<(int)a[nod].size();j++){
			int vecin = a[nod][j].first;
			int cost = a[nod][j].second;
			if(d[nod]+cost<d[vecin]){
				d[vecin]=d[nod]+cost; 
				insert_heap(vecin,d[vecin],heap_size);
			}
		}	
	}
	
	for(i=2;i<=n;i++)
	  if(d[i]==INF) fo<<"0 ";
	  else fo<<d[i]<<" ";
	
	fi.close();
	fo.close();
	return 0;
}