#include <set>
#include <cassert>
#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 + 2;
int d[N];
int seen[N];


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] = 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 to = e.to;
      int c = e.c;
      if (seen[to] != 1 && d[to] > d[node] + c) {
	d[to] = d[node] + c;
	q.insert(make_pair(d[to], to));
      }
    }
    
  }

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