#include <fstream>
#include <vector>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int MAX = (5e4 + 5);
const int INF = (1e9);

template < class Type >

class Heap {
public:
  
  Heap(): _MAX(25e4 + 5) {
    this -> _arr.resize(_MAX);
    this -> _heap.resize(_MAX);
    this -> _arr_size = 0;
    this -> _heap_size = 0;
  }

  bool empty() {
    return _heap_size == 0;
  }

  int size() {
    return _heap_size;
  }

  Type push(Type x) {
    _push(x);
  }

  void pop() {
    _pop();
  }

  Type top() {
    return _arr[_heap[1]];
  }
private:

  const int _MAX;
  vector < int > _heap;
  vector < Type > _arr;
  int _heap_size;
  int _arr_size;

  void _repair(int node) {
    if ((node << 1 | 1) <= _heap_size) {
      if (_arr[_heap[node]] > min(_arr[_heap[node << 1]], _arr[_heap[node << 1 | 1]])) {
        if (_arr[_heap[node << 1]] <= _arr[_heap[node << 1 | 1]]) {
          swap(_heap[node], _heap[node << 1]);
          _repair(node << 1);
        }
        else {
          swap(_heap[node], _heap[node << 1 | 1]);
          _repair(node << 1 | 1);
        }
      }
      return;
    }
    else if ((node << 1) == _heap_size) {
      if (_arr[_heap[node]] > _arr[_heap[node << 1]]) {
        swap(_heap[node], _heap[node << 1]);
      }
      return;
    }
    else if (node << 1 > _heap_size) {
      return;
    }
  }

  void _pop() {
    swap(this -> _heap[1], this -> _heap[this -> _heap_size --]);
    this -> _repair(1);
  }

  void _set_poz(int node) {
    if (_arr[_heap[node]] >= _arr[_heap[node >> 1]] or node == 1) {
      return;
    }

    swap(_heap[node], _heap[node >> 1]);
    _set_poz(node >> 1);
  }

  void _push(Type x) {
    _arr[++ _arr_size] = x;
    _heap[++ _heap_size] = _arr_size;
    _set_poz(_heap_size);
  }
}; 

int main() {
  Heap < pair < int, int > >  *h = new Heap < pair < int, int > > ();
  vector < vector < pair < int, int > > > node(MAX);
  vector < int > dist(MAX, INF);
  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= m; i ++) {
    int a, b, cost;
    cin >> a >> b >> cost;
    node[a].push_back({cost, b});
  }

  dist[1] = 0;
  h -> push({0, 1});

  while (!h -> empty()) {
    pair < int, int > cur = h -> top();
    int cur_dist = cur.first;
    int cur_node = cur.second;
    h -> pop();
    if (dist[cur_node] != cur_dist) {
      continue;
    }

    for (auto x : node[cur_node]) {
      if (cur_dist + x.first < dist[x.second]) {
        dist[x.second] = cur_dist + x.first;
        h -> push({dist[x.second], x.second});
      }
    }
  }

  for (int i = 2; i <= n; i ++) {
    if (dist[i] == INF)
      cout << 0 << ' ';
    else 
      cout << dist[i] << ' ';
  }

  cout << '\n';
  delete h;
}