#include<fstream>
#include<vector>
#include<deque>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int inf=1e9;
int n,m,x,b,cc;
struct muchie
{
    int y,c;
};
vector<muchie>a[50005];
deque<int>q;
int dist[50005],cont[50005];
bool ciclu;
muchie construieste_muchia(int &a,int &b)
{
    muchie rez;
    rez.y=a;
    rez.c=b;
    return rez;
}
void bell()
{
    int poz;
    q.push_back(1);
    for(int i=0;i<=n;i++)
      dist[i]=inf;
    dist[1]=0;
    while(!q.empty())
    {
        poz=q.front();
        q.pop_front();
        for(int i=0;i<a[poz].size()&&ciclu==0;i++)
        {
            if(dist[a[poz][i].y]<dist[poz]+a[poz][i].c&&ciclu==0)
            {
                dist[a[poz][i].y]=dist[poz]+a[poz][i].c;
                q.push_back(a[poz][i].y);
                cont[a[poz][i].y]++;
                if(cont[a[poz][i].y]>n)
                  ciclu=1;
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>b>>cc;
        a[x].push_back(construieste_muchia(b,cc));
    }
    bell();
    if(ciclu==0)
      for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
    else
      g<<"Ciclu Negativ!";
    return 0;
}