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

struct edge {
	int to, cost;
	edge* next;
};

const int NMAX = 50001;
const int INF = 1<<29;
int N, M, heap_size, dist[NMAX], heap[NMAX], poz[NMAX];
edge* 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;	
		edge* newEdge = new edge();
		newEdge->to = to; newEdge->cost = cost;
		newEdge->next = adj_list[from];
		adj_list[from] = newEdge;
	}
	f.close();
}

void move_up(int i) {
	int parent = i>>1;
	while (parent > 0 && dist[heap[parent]] > dist[heap[i]]) {
		swap(heap[parent],heap[i]);
		swap(poz[heap[parent]],poz[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(heap[i],heap[smallest]);
		swap(poz[heap[i]],poz[heap[smallest]]);		
		i = smallest;
  }while(true);
}

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

void djikstra() {
	int i, u;
	list<pair<int, int> >::iterator it;
    for (i=1;i<=N;i++) {
		heap[i] = poz[i] = i;
        dist[i] = INF;
    }
	dist[1] = 0;  heap_size=N;
    for (i=1;i<=N;i++) {
      u = extract_min();
	  for (edge* it = adj_list[u];it!=NULL;it = it->next) 
	  {
		if (dist[it->to] > dist[u]+it->cost) {		    
			dist[heap[poz[it->to]]] = dist[u]+it->cost;
			move_up(poz[it->to]);
        }
      }
	}  
}

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;
}