#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 5e4;
const int INF = 5e8;

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

struct Edge {
  int node, cost;
};

vector <Edge> graph[MAX_N];
queue <int> bfQueue;
int dist[MAX_N], marked[MAX_N], counter[MAX_N];
int n;

void addEdge( int a, int b, int cost ) {
  graph[a].push_back({b, cost});
}

void bf( int node ) {
  int i, qFront;

  for( i = 0; i < n; i++ )
    marked[i] = false, dist[i] = INF;

  dist[node] = 0;
  ++counter[node];

  bfQueue.push(node);
  marked[node] = true;

  while( !bfQueue.empty() && counter[qFront = bfQueue.front()] < n ) {
    for( const Edge& edge : graph[qFront] ) {
      if( dist[edge.node] > dist[qFront] + edge.cost ) {
        dist[edge.node] = dist[qFront] + edge.cost;
        ++counter[edge.node];

        if( !marked[edge.node] ) {
          bfQueue.push(edge.node);
          marked[edge.node] = true;
        }
      }
    }
    marked[qFront] = false;
    bfQueue.pop();
  }

  if( !bfQueue.empty() )
    cout << "Ciclu negativ!\n";
}

int main() {
  int m, x, y, c, i;
  fin >> n >> m;
  for( i = 0; i < m; i++ ) {
    fin >> x >> y >> c;
    x--;
    y--;
    addEdge( x, y, c );
  }
  bf( 0 );
  for( i = 1; i < n; i++ )
    fout << dist[i] << " ";
  return 0;
}