#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <queue>
#define inf=INT_MAX
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair <int, int> > L[50001];
queue <int> Q;
int D[50001], S[50001], n, m, Count[50001];
void Citire()
{int i, x, y , c;
    f>>n>>m;
 for(i=1;i<=m;i++)
 {f>>x>>y>>c;
     L[x].push_back(make_pair(y,c));
 }
}
void Bellman_Ford()
{ int i, j, k,ok;
    for(i=1;i<=n;i++)
        D[i]=INT_MAX;
    D[1]=0; Q.push(1);
    ok=0;
    while((!Q.empty())&&(ok==0))
    { int x=Q.front();
       Q.pop();
             for(k=0;k<L[x].size();k++)
               if(D[x]!=INT_MAX&&D[L[x][k].first]>D[x]+L[x][k].second)
                 { int nr=L[x][k].first;
                    if(Count[nr]>=n)
                      ok=1;
                    else{
                   D[L[x][k].first]=D[x]+L[x][k].second;
                  Q.push(nr);
                  Count[nr]++;}
                 }
    }
if(ok==1)
    g<<"Ciclu negativ!";
else  {
        for(i=2;i<=n;i++)
      g<<D[i]<<" ";
      }
}


int main()
{
Citire();

Bellman_Ford();

f.close();
g.close();
    return 0;
}