#include<bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;
const int oo = (1 << 30);

int n, m, i, j;
int distanta[NMAX];

bool in_coada[NMAX];

vector < pair < int, int > > v[NMAX];

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

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

void Dijkstra(int nod_start) {
  distanta[nod_start] = 0;

  coada.push(nod_start);
  in_coada[nod_start] = true;

  while (!coada.empty()) {
    int nod_curent = coada.top();
    coada.pop();

    in_coada[nod_curent] = false;

    for (unsigned int i = 0; i < v[nod_curent].size(); i++) {
      int vecin = v[nod_curent][i].first;
      int cost = v[nod_curent][i].second;
      if (distanta[nod_curent] + cost < distanta[vecin]) {
        distanta[vecin] = distanta[nod_curent] + cost;
        if (in_coada[vecin] == false) {
          in_coada[vecin] = true;
          coada.push(vecin);
        }
      }
    }
  }
}

int main() {
  fin >> n >> m;
  for (i = 1; i <= m; i++) {
    int a, b, c;
    fin >> a >> b >> c;
    v[a].push_back(make_pair(b, c));
  }

  for (i = 1; i <= n; i++)
    distanta[i] = oo;

  Dijkstra(1);

  for (i = 2; i <= n; i++)
    if (distanta[i] != oo)
      fout << distanta[i] << " ";
    else
      fout << "0 ";
}