#include <fstream>
#include <list>
using namespace std;

const int NMAX = 50001;
const int INF = 1<<29;
int N, M, heap_size, dist[NMAX], heap[NMAX], poz[NMAX];
list<pair<int, int> > adj_list[NMAX];

void readInput() {	
	int from, to, cost;
	ifstream f("dijkstra.in");
	f>>N>>M;
	for (int i=1;i<=M;i++) {
		f>>from>>to>>cost;		
		adj_list[from].push_back(make_pair(to,cost));		
	}
	f.close();
}

void move_up(int i) {
	int parent = i>>1;
	while (parent > 0 && dist[heap[parent]] > dist[heap[i]]) {
		swap(poz[heap[parent]],poz[heap[i]]);
		swap(heap[parent],heap[i]);		
		i = parent;
		parent = i>>1;
	}
}

void move_down(int i) {
	int smallest, left;
	do	{
		smallest = i; 
		left=i<<1;
		for (int k=left;k<=left+1;k++) {
		  if (k <= heap_size && dist[heap[k]] < dist[heap[smallest]]) {
			  smallest = k;
		  }
		}
		if (smallest == i) return;
		swap(poz[heap[i]],poz[heap[smallest]]);		
		swap(heap[i],heap[smallest]);	
		i = smallest;
  }while(true);
}

int extract_min() {
	int x = heap[1];
	swap(poz[heap[1]],poz[heap[heap_size]]);
	swap(heap[1],heap[heap_size]); 
	heap_size--;
	move_down(1);
	return x;
}

void djikstra() {
	int i, u;
	list<pair<int, int> >::iterator it;
    for (i=1;i<=N;i++) {
		dist[i] = INF;		
		//heap[i] = poz[i] = i;       
    }
	dist[1] = 0;  
	
	for (int i=1;i<=N;i++) {
		heap[++heap_size] = i;
		poz[i] = i;
		move_up(i);
	}

	while (heap_size>0) {
	  u = extract_min();/*heap[1];
	  swap(heap[1],heap[heap_size--]);
	  poz[heap[1]]=1;
	  move_down(1);*/
      for (it = adj_list[u].begin();it!=adj_list[u].end();it++) 
	  {
		if (dist[it->first] > dist[u]+it->second) {		    
			dist[heap[poz[it->first]]] = dist[u]+it->second;
			move_up(poz[it->first]);
        }
      }
	}  
}

int main() {
	readInput();
	ofstream g("dijkstra.out");
	djikstra();
	for (int i=2;i<=N;i++) {
		g<<((dist[i]<INF)?dist[i]:0)<<" ";
	}
	g<<"\n";
	return 0;
}