#include <stdio.h>
#include <queue>
#include <vector>

const int MAXN = 1e5;
std::vector<std::pair<int, int>> adj[MAXN];
int dist[MAXN];

int main() {
  FILE *fin = fopen( "dijkstra.in", "r" );
  FILE *fout = fopen( "dijkstra.out", "w" );

  int n, m;
  fscanf( fin, "%d%d", &n, &m );

  for( int i = 0; i < m; i++ ){
    int a, b, cost;
    fscanf( fin, "%d%d %d", &a, &b, &cost );
    a--; b--;
    adj[a].emplace_back( b, cost );
  }

  std::priority_queue<std::pair<int, int>> pq;
  pq.emplace( -(dist[0] = 0), 0 );
  while( !pq.empty() ){
    auto [mdist, u] = pq.top();
    pq.pop();
    if( -dist[u] != mdist ) continue;

    for( auto [v, cost]: adj[u] )
      if( dist[u] + cost < dist[v] )
        pq.emplace( -(dist[v] = dist[u] + cost), v );
  }

  for( int i = 0; i < n; i++ )
    fprintf( fout, "%d ", dist[i] );
  fputc( '\n', fout );
  
  fclose( fin );
  fclose( fout );
  return 0;
}