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

using namespace std;

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

struct lol{
  int nod, cost;
  bool operator<( const lol &value ) const{
    return cost > value.cost;
  }
};

const int NMAX = 5e4;
vector <lol> graf[NMAX + 2];
priority_queue <lol> pq;
int dist[NMAX + 1];
bool viz[NMAX + 1];

void dijkstra( int start, int n ){
  for( int i = 1; i <= n; ++i )
    dist[i] = 2e9;
  pq.push({start, 0});
  dist[start] = 0;
  while( !pq.empty() ){
    int nods = pq.top().nod;
    pq.pop();
    if( !viz[nods] ){
      viz[nods] = 1;
      for( int i = 0; i < graf[nods].size(); ++i ){
        int cost = graf[nods][i].cost;
        if( dist[graf[nods][i].nod] > dist[nods] + cost ){
          dist[graf[nods][i].nod] = dist[nods] + cost;
          pq.push({graf[nods][i].nod, dist[graf[nods][i].nod]});
        }
      }
    }
  }
  for( int i = 2; i <= n; ++i )
    if( dist[i] == 2e9 )
      fout << "0 ";
    else
      fout << dist[i] << " ";
}

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