#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
int n,m,i,co,tata[50001],d[10001],k,j,x,okay,y;
short c[10001][10001];
int INF=1000001;
int bellmanford(int x0)
{
    int ok,i,j,k;
    for(i=1;i<=n;i++)
    {
        tata[i]=0;
        d[i]=INF;
    }
    d[x0]=0;
    for(i=1;i<=n;i++)
    {
        ok=0;
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                if(d[j]!=INF && c[j][k]!=INF)
                    if(d[k]>d[j]+c[j][k])
        {
            d[k]=d[j]+c[j][k];
            tata[k]=j;
            ok=1;
           // if(i==1 )
               // cout<<d[i]<<endl;
        }
 //if(i==1 )
               if(okay==1 && i!=1) g<<d[i]<<" ";
    }
    return ok;

}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            c[i][j]=INF;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>co;
        c[x][y]=co;
    }
    for(i=1;i<=n;i++)
    {
        if(!bellmanford(i)) k++;
    }
    if(k!=0) {okay=1;bellmanford(1);}
    else g<<"Ciclu negativ!";

    return 0;
}