#include <cstdio>
#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;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&N,&M);
	for (int i=1;i<=M;i++) {
		scanf("%d %d %d",&from,&to,&cost);
		adj_list[from].push_back(make_pair(to,cost));		
	}
}

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=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) {
//	  swap(heap[i],heap[smallest]);
//	  swap(poz[heap[i]],poz[heap[smallest]]);
//	  move_down(smallest);
//  }
//}

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;
    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++) {
      int u = extract_min();
      for (list<pair<int, int> >::iterator 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();
	freopen("dijkstra.out","w",stdout);
	djikstra();
	for (int i=2;i<=N;i++) {
		printf("%d ",(dist[i]<INF)?dist[i]:0);
	}
	printf("\n");
	return 0;
}