#define _USE_MATH_DEFINES
#include <fstream>
#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#define nmax 250005
 
using namespace std;
 
vector < pair <int,int> > v[nmax];
queue <int> q;
bool in_q[nmax];
int n,m;
int d[nmax],cnt_q[nmax];
 
bool Push();
bool Bellman_Ford();
 
int main(){
  int x,y,cost;
  freopen("bellmanford.in","r",stdin);
  freopen("bellmanford.out","w",stdout);
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>x>>y>>cost;
    v[x].push_back(make_pair(y,cost));
  }
  if(!Bellman_Ford())
    {
      cout<<"Ciclu negativ!";
      return 0;
    }
      for(int i=2;i<=n;i++)
	cout<<(d[i]==INT_MAX?0:d[i])<<' ';
  return 0;
}
 
inline bool  Push(int x){
  cnt_q[x]++;
  if(cnt_q[x]>n) return false;
  if(!in_q[x]){
  q.push(x);
  in_q[x]=1;
  }
  return true;
}
 
 
bool Bellman_Ford(){
  int now;
  for(int i=0;i<=n;i++)
    d[i]=INT_MAX;
  Push(1);
  d[1]=0;
  while(!q.empty()){
    now=q.front();
    q.pop();
    in_q[now]=0;
    for(int i=0;i<v[now].size();i++){
      int next=v[now][i].first;
      int cost=v[now][i].second;
      if(d[now]+cost<d[next]){
        d[next]=d[now]+cost;
        if(!Push(next)) return false;
      }
    }
  }
  return true; 
}