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

using namespace std;

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

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

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

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

  dist[nod] = 0;
  PQ.push({0, nod});  //retin costul pana la nodul curent;
  while(!PQ.empty()) {
    int node = PQ.top().second;
    int cost = PQ.top().first;
    PQ.pop();

    if(cost > dist[node])
      continue;
    
    for(auto e : G[node])
      if(cost + e.second < dist[e.first]) {
        dist[e.first] = cost + e.second;
        PQ.push({dist[e.first], e.first});
      }
  }
}

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

  Dijkstra(1);

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

  return 0;
}