#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;
int n;

void dijkstra( int nod ) {
  int i;
  for( i = 0; i < n; i++ )
    dist[i] = -2e9;
  pq.push( { -1, nod } );
  while( !pq.empty() ) {
    pair <int, int> qfront = pq.top();
    pq.pop();
    for( auto neighbour: edges[qfront.second] ) {
      if( dist[neighbour.node] < qfront.first - neighbour.cost ) {
        pq.push( { qfront.first - neighbour.cost, neighbour.node } );
        dist[neighbour.node] = qfront.first - neighbour.cost;
      }
    }
  }
}
int main() {
  int 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++ ) {
    if( -dist[i] != 2e9 )
      fout << -dist[i] - 1 << " ";
    else
      fout << "0 ";
  }
  return 0;
}