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

const int oo = (1 << 30);

int nodes, edges, k, d[250000];
bool in_q[250000];

vector<pair<int, int>> gr[250000];
priority_queue< int, vector<int> > q;

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

void dijkstra(int nodStart) {
  for (int i = 1; i <= nodes; 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] = cost + d[nodCurent];
        if (in_q[vecin] == false) {
          q.push(vecin);
          in_q[vecin] = true;
        }
      }
    }
  }
}

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

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