#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4;

struct lol{
  int cost, nod;
  bool operator < ( const lol &x ) const {
    return cost > x.cost;
  }
};
int dist[NMAX + 1];
vector <pair<int, int>> v[NMAX + 1];
priority_queue <lol> pq;
bitset <NMAX + 1> viz;

int main() {
  int n, m, i, x, y, costx, node;
  fin >> n >> m;
  for( i = 0; i < m; ++i ){
    fin >> x >> y >> costx;
    v[x].push_back({y, costx});
  }
  for( i = 0; i <= n; ++i )
    dist[i] = (1 << 30);
  pq.push({0, 1});
  dist[1] = 0;
  while( !pq.empty() ){
    node = pq.top().nod;
    pq.pop();
    if( !viz[node] ){
      for( i = 0; i < v[node].size(); ++i )
        if( dist[v[node][i].first] > dist[node] + v[node][i].second ){
          dist[v[node][i].first] = dist[node] + v[node][i].second;
          pq.push({dist[v[node][i].first], v[node][i].first});
        }
    }
  }
  for( i = 2; i <= n; ++i ){
    if( dist[i] == (1 << 30) )
      dist[i] = 0;
    fout << dist[i] << " ";
  }
  fout << "\n";
  return 0;
}