#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 50000
#define MAXQ (1<<18)
#define INF 1000000000
FILE*fi,*fout;
using namespace std;
class Muchie{
  public :
    int nod;
    int cost;
};
vector <Muchie> G[MAXN+1];
int dist[MAXN+1];
int cod[MAXQ];
int vf[MAXN+1];
char good[MAXN+1];
inline void Bellman_Ford(int n){
    int i,b,e,nod;
    for(i=2;i<=n;i++)
      dist[i]=INF;
    cod[0]=1;
    good[1]=1;
    vf[1]=1;
    b=0;
    e=1;
    while(b<e&&vf[cod[b%MAXQ]]<n){
        good[cod[b%MAXQ]]=0;
        nod=cod[b%MAXQ];
        for(i=0;i<G[nod].size();i++)
          if(dist[G[nod][i].nod]>dist[nod]+G[nod][i].cost){
            dist[G[nod][i].nod]=dist[nod]+G[nod][i].cost;
            if(good[G[nod][i].nod]==0){
               good[G[nod][i].nod]=1;
               cod[e%MAXQ]=G[nod][i].nod;
               vf[cod[e%MAXQ]]++;
               e++;
            }
        }
        b++;
    }
    if(vf[cod[b%MAXQ]]==n)
      fprintf(fout,"Ciclu negativ!");
    else
      for(i=2;i<=n;i++)
        fprintf(fout,"%d " ,dist[i]);
}
int main(){
   int n,m,a,b,c,i;
   fi=fopen("bellmanford.in" ,"r");
   fout=fopen("bellmanford.out" ,"w");
   fscanf(fi,"%d%d" ,&n,&m);
   for(i=0;i<m;i++){
      fscanf(fi,"%d%d%d" ,&a,&b,&c);
      Muchie x;
      x.nod=b;
      x.cost=c;
      G[a].push_back(x);
   }
   Bellman_Ford(n);
   fclose(fi);
   fclose(fout);
   return 0;
}