#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 interschimba(int *a, int*b) {
	int tmp = *a; *a = *b; *b = tmp;
}

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

void move_down(int i) {
  int smallest=i, left=i<<1, right=left+1;
  if (left <= heap_size && dist[heap[left]] < dist[heap[smallest]]) {
	  smallest = left;
  }
  if (right <= heap_size && dist[heap[right]] < dist[heap[smallest]]) {
	  smallest = right;
  }
  if (smallest != i) {
	  interschimba(&heap[i],&heap[smallest]);
	  poz[heap[i]] = i;
	  poz[heap[smallest]] = smallest;
	  move_down(smallest);
  }
}

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

void decreaseKey(int i, int val) {
	dist[heap[i]] = val;
	move_up(i);
}

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 (it->first == 3)	{
		  int a = 3;
		  a = 5;
		}

        if (dist[it->first] > dist[u]+it->second) {
		    decreaseKey(poz[it->first], dist[u]+it->second);
        }
      }
	}  
}

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