#include <bits/stdc++.h>

using namespace std;

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

const int INF = (1 << 30);

vector<pair<int, int> >V[50002];

int Dist[50002];

bool inCoada[50002];

struct Comp {
  bool operator() (const int &x, const int &y) {
    return Dist[x] > Dist[y];
  }
};

priority_queue<int, vector<int>, Comp>pq;

int n, m, x, y, c;

void Citire () {
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y >> c;
    V[x].push_back(make_pair(y, c));
  }
}

void Afiseaza () {
  for (int i = 2; i <= n; i++) {
    if (Dist[i] != INF)
      fout << Dist[i] << " ";
    else
      fout << "0 ";
  }
}

void Dijkstra (int nod) {
  for (int i = 1; i<= n; i++)
    Dist[i] = INF;
  Dist[nod] = 0;
  pq.push(1); inCoada[1] = true;
  while (!pq.empty()) {
    int nodNou = pq.top();
    pq.pop();
    inCoada[nodNou] = false;
    for (unsigned int i = 0; i < V[nodNou].size(); i++) {
      int Vecin = V[nodNou][i].first;
      int Cost = V[nodNou][i].second;
      if (Dist[nodNou] + Cost < Dist[Vecin]) {
        Dist[Vecin] = Dist[nodNou] + Cost;
        if (inCoada[Vecin] == false) {
          pq.push(Vecin);
          inCoada[Vecin] = true;
        }
      }
    }
  }
}
int main()
{
  Citire();
  Dijkstra(1);
  Afiseaza();
  return 0;
}