#include<bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define MAX_N 50000
int n, m;
vector< pair<int, int> > graph[MAX_N];
bool marked[MAX_N];
int d[MAX_N];

struct cmp {
  bool operator() (int x, int y) {
    return d[x] > d[y];
  }
};

void dijkstra() {
  for (int i = 0; i < MAX_N; ++i) {
    d[i] = INT_MAX;
  }

  priority_queue<int, vector<int>, cmp> heap;
  d[0] = 0;
  heap.push(0);
  marked[0] = true;

  while (!heap.empty()) {
    int node = heap.top();
    heap.pop();

    for (auto neighbour : graph[node]) {
      if (d[neighbour.first] <= d[node] + neighbour.second)
        continue;

      d[neighbour.first] = d[node] + neighbour.second;
      if (!marked[neighbour.first]) {
        heap.push(neighbour.first);
        marked[neighbour.first] = true;
      }
    }

    marked[node] = false;
  }
}

int main() {
  fin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y, c;
    fin >> x >> y >> c;
    --x, --y;

    graph[x].push_back( {y, c} );
  }

  dijkstra();

  for (int i = 1; i < n; ++i) {
    fout << (d[i] == INT_MAX ? 0 : d[i]) << " ";
  }
}