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


using namespace std;

#define DBG(x) // std::cout << #x << ":" << x << std::endl;


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

};

const int N = 50000 + 1;

long long d[N];
struct comparator {		    
  bool operator() (const long long& lhs, const long long& rhs) {
    return d[lhs] > d[rhs];
  }
};


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

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

  scanf("%d %d", &n, &m);
  const int N = n + 1;

  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] = LLONG_MAX;

  d[1] = 0;

  priority_queue<long long, vector<int>, comparator> q;
  q.push(1ll);
  int seen[N];
  memset(seen, 0, sizeof(int) * N);

  while (!q.empty()) {
    DBG("HERE-s");
    DBG(q.size());
    
    int tos = q.top(); q.pop();
    
    if (seen[tos]) continue;
    seen[tos] = 1;

    DBG(tos);


    for (int i = 0; i < nodes[tos].size(); i++) {
      edge e = nodes[tos][i];
      int c = e.c;
      int to = e.to;
      DBG(to);
      DBG(d[tos]);
      DBG(c);
      if (d[to] > d[tos] + c) {
	d[to] = d[tos] + c;
	q.push(to);
	DBG("HERE");
      }
    }
    
    DBG("ds");
    /*
    for (int i = 2; i <= n; i++) {
      printf("%d ", d[i]);
  }
  printf("\n");*/
  }

  for (int i = 2; i <= n; i++) {
    if (d[i] == LLONG_MAX)
      printf("%lld ", 0ll);
    else
      printf("%lld ", d[i]);
  }
  printf("\n");
  
  return 0;
}