#include <vector>
#include <fstream>
#include <queue>
#include <functional>

#define INF 1000000000

using namespace std;

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

int dist[500001];

bool vis[500001];

vector < pair<int, int> > ponderi[500001];

priority_queue < pair<int, int>, vector< pair<int, int> >, greater < pair<int, int> > > Q;

int main() {

  int n, m;
  fin >> n >> m;

  int start = 1;

  for (int i = 1; i <= m; ++i) {
    int nod1, nod2, pondere;
    fin >> nod1 >> nod2 >> pondere;
    ponderi[nod1].push_back({nod2, pondere});
  }

  // initializari
  for (int i = 1; i <= n; ++i) {
    dist[i] = INF;
    vis[i] = false;
  }
  dist[start] = 0;
  Q.push({0, start});

  while (!Q.empty()) {
    pair<int, int> top = Q.top();
    Q.pop();

    int nod_minim = top.second;
    if(vis[nod_minim])
      continue;

    vis[nod_minim] = true;

    for (int v = 0; v < ponderi[nod_minim].size(); ++v) {
      int vecin = ponderi[nod_minim][v].first;
      int pondere = ponderi[nod_minim][v].second;

      if (vis[vecin] == false && dist[vecin] > dist[nod_minim] + pondere) {
        dist[vecin] = dist[nod_minim] + pondere;
        Q.push({dist[vecin], vecin});
      }
    }

    }



  // afisare
  for (int i = 1; i <= n; ++i) {
    if (i != start) {
      fout << dist[i] << " ";
    }
  }

}