#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int a[100][100], n,m,viz[100],d[100],t[100],start;
void citire()
{
    fin>>n>>m;
    int x, y, c;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        a[x][y]=c;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j && a[i][j]==0)
                a[i][j]=inf;
        }
    }
    start=1;
}
void init()
{
    viz[start]=1;
    for(int i=1;i<=n;i++)
    {
        d[i]=a[start][i];
        t[i]=start;
    }
    t[start]=0;
}
int bellmanford()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]!=inf && d[j]>d[i]+a[i][j])
                {
                    d[j]=d[i]+a[i][j];
                    t[j]=i;
                }
            }
        }
    }
    for(int i=1;i<n;i++)
        for(int j=1;j<=n;j++)
          if(a[i][j]!=inf && d[j]>d[i]+a[i][j])
              return 0;
    return 1;
}
int main()
{
    citire();
    init();
    if (bellmanford() == 0)
        fout<<"Ciclu negativ";
    else
        for (int j=2;j<=n;j++)
            fout<<d[j]<<" ";
    return 0;
}