#include <set>
#include <cassert>
#include <cstring>
#include <climits>
#include <vector>
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

const int N = 50000 + 2;
int d[N], seen[N];

struct edge {
  int from, to, c;
  edge(int from, int to, int c) {
    this->from = from;
    this->to = to;
    this->c = c;
  }

};

int main(int argc, char *argv[])
{
  int n, m;

  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  scanf("%d %d", &n, &m);

  vector<edge> nodes[N];
  for (int i = 0; i < m; i++) {
    int from, to, c;
    scanf("%d %d %d", &from, &to, &c);
    edge e(from, to, c);
    nodes[from].push_back(e);
  }

  for (int i = 0; i <= n; i++) 
    d[i] = INT_MAX;

  d[1] = 0;

  set<pair<int, int> > q;
  q.insert(make_pair(0, 1));

  while (!q.empty()) {
    pair<int, int> best = *(q.begin()); 
    int node = best.second;

    q.erase(q.find(best));
    
    if (seen[node] == 1) continue;
    seen[node] = 1;

    for (int i = 0; i < nodes[node].size(); i++) {
      edge e = nodes[node][i];	
      int alt = d[node] + e.c;
      int to = e.to;
      if (seen[to] != 1 && d[to] > alt) {
	d[to] = alt;
	q.insert(make_pair(d[to], to));
      }
    }
  }

  for (int i = 2; i <= n; i++)
    printf("%d ", d[i] == INT_MAX ? 0 : d[i]);
  printf("\n");
  
  return 0;
}