#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e5;
bitset <NMAX + 1> inqueue;
queue <int> q;
vector <pair<int, int>> v[NMAX + 1];
int dist[NMAX + 1];

int main(){
  int n, m, i, x, y, cost;
  fin >> n >> m;
  for( i = 0; i < m; ++i ){
    fin >> x >> y >> cost;
    v[x].push_back({y, cost});
  }
  for( i = 0; i <= NMAX; ++i )
    dist[i] = (1<<30);
  q.push(1);
  inqueue[1] = 1;
  dist[1] = 0; 
  while( !q.empty() ){
    int nod = q.front();
    q.pop();
    inqueue[nod] = 0;
    for( i = 0; i < v[nod].size(); ++i ){
      if( dist[v[nod][i].first] > dist[nod] + v[nod][i].second ){
        dist[v[nod][i].first] = dist[nod] + v[nod][i].second;
        if( !inqueue[v[nod][i].first] ){
          inqueue[v[nod][i].first] = 1;
          q.push(v[nod][i].first);
        }
      }
    }
  }
  for( i = 2; i <= n; ++i ){
    if( dist[i] == (1 << 30) )
      dist[i] = 0;
    fout << dist[i] << " ";
  }
  return 0;
}