#include<fstream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,i,j,d[50001];
const int INF=2e9;
struct muchie
{
    int x,y,cost;
};
muchie v[250001];
int main()
{
    fin>>n>>m;
    fill(d+2,d+n+1,INF);
    for(i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    for(i=1;i<n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(d[v[j].x]!=INF)
                if(d[v[j].x]+v[j].cost<d[v[j].y])
                {
                    d[v[j].y]=d[v[j].x]+v[j].cost;
                }
        }
    }
    for(j=1;j<=m;j++)
    {
        if(d[v[j].x]!=INF)
            if(d[v[j].x]+v[j].cost<d[v[j].y])
            {
                fout<<"Ciclu negativ!";
                return 0;
            }
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<" ";

}