#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 5e4;

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

struct Edge{
  int node;
  int cost;
};
vector <Edge> edges[NMAX];
int dist[NMAX];
priority_queue < pair<int, int> > pq;

void dijkstra( int nod ) {
  pq.push( { -1, nod } );
  while( !pq.empty() ) {
    pair <int, int> qfront = pq.top();
    pq.pop();
    if( !dist[qfront.second] )
      dist[qfront.second] = qfront.first;
    for( auto neighbour: edges[qfront.second] ) {
      if( !dist[neighbour.node] )
        pq.push( { qfront.first - neighbour.cost, neighbour.node } );
    }
  }
}
int main() {
  int n, m, i, a, b, c;
  fin >> n >> m;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b >> c;
    a--;
    b--;
    edges[a].push_back( { b, c } );
  }
  dijkstra( 0 );
  for( i = 1; i < n; i++ )
    fout << -dist[i] - 1 << " ";
  return 0;
}