#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

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

#define DIM 50000
#define INF (1 << 30)
typedef pair<int, int> PII;

int n, m, d[DIM + 1];
priority_queue <PII, vector<PII>, greater<PII>> q;
vector <PII> G[DIM + 1];

static inline void Dijkstra(int nod) {
  for(int i = 1; i <= n; i++)
    d[i] = INF;

  d[nod] = 0;
  q.push({0, nod}); //costul si nodul;
  while(!q.empty()) {
    int dist = q.top().first;
    int nod = q.top().second;
    q.pop();

    if(dist > d[nod])
      continue;
    
    for(auto e : G[nod])
      if(d[e.first] > dist + e.second) {
        d[e.first] = dist + e.second;
        q.push({d[e.first], e.first});
      }
  }
}

int main() {
  int x, y, z;
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    fin >> x >> y >> z;
    G[x].push_back({y, z}); //unde merg si costul;
  }

  Dijkstra(1);
  for(int i = 2; i <= n; i++) 
    fout << (d[i] == INF ? 0 : d[i]) << " ";

  return 0;
}