#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 250005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int oo = (1 << 30);

int n, m, d[NMAX];
vector<pair<int, int>> gr[NMAX];
bool in_q[NMAX];

void citire() {
  fin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, cost;
    fin >> x >> y >> cost;
    gr[x].push_back(make_pair(y, cost));
  }
}

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

priority_queue<int, vector<int>, compara> q;

void minCost(int nodStart) {
  for (int i = 1; i <= n; i++)
    d[i] = oo;
  d[nodStart] = 0;
  q.push(nodStart);
  in_q[nodStart] = true;
  
  while (!q.empty()) {
    int nodCurent = q.top();
    q.pop();
    in_q[nodCurent] = false;
    
    for (int i = 0; i < gr[nodCurent].size(); i++) {
      int vecin = gr[nodCurent][i].first;
      int cost = gr[nodCurent][i].second;
      
      if (d[nodCurent] + cost < d[vecin]) {
        d[vecin] = d[nodCurent] + cost;
        if (in_q[vecin] == false) {
          q.push(vecin);
          in_q[vecin] = true;
        }
      }
    }
  }
}

void afisare() {
  for (int i = 2; i <= n; i++)
    if (d[i] != oo)
      fout << d[i] << " ";
    else
      fout << 0 << " ";
}

int main(int argc, const char * argv[]) {
  citire();
  minCost(1);
  afisare();
}