#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#define INF 1<<30
using namespace std;
ifstream f("bellmanfort.in");
ofstream g("bellmanfort.out");

int n, m, costMin[50005], y1, y2, node, new_node;
struct element{
  int vecin, cost;
}x;
vector <element> v[50005];
queue <int> C;
void read(){
 f >> n >> m;
 for(int i = 1; i <= m; ++i){
    f >> y1 >> y2 >> x.cost;
    x.vecin = y2;
    v[y1].push_back(x);
 }
}
void bfs(int i){
  node = i;
  C.push(node);
  while(!C.empty()){
    node = C.front();
    for(int i = 0; i < v[node].size(); ++i){
        new_node = v[node][i].vecin;
        if(costMin[node] + v[node][i].cost < costMin[new_node]){
        costMin[new_node] = costMin[node] + v[node][i].cost;
        C.push(new_node);
      }
    }
   C.pop();
  }
}
int is_negative(){
  for(int i = 1; i <= n; ++i)
    for(int j = 0; j < v[i].size(); ++j)
       if(costMin[v[i][j].vecin] > costMin[i] + v[i][j].cost)
       return 1;
  return 0;
}
void write(){
 if(is_negative())
    g << "Ciclu negativ!";
 else
  for(int i = 2; i <= n; ++i)
     g << costMin[i] << ' ';
}
int main()
{
    read();
    for(int i = 2; i <= n; ++i)
        costMin[i] = INF;
    bfs(1);
    write();
    return 0;
}