#include<fstream>
using namespace std;

int n,m,L[3][250002],d[50002];
int main()
{
    int i,k,ok;
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>L[0][i]>>L[1][i]>>L[2][i];
    }
    for (i=2;i<=n;i++)
    {
        d[i]=1000000000;
    }
    d[1]=0;
    k=0;
    do
    {
        ok=1;
        for (i=1;i<=m;i++)
        {
            if (d[L[0][i]]+L[2][i]<d[L[1][i]])
            {
                ok=0;
                d[L[1][i]]=d[L[0][i]]+L[2][i];
            }
        }
        k++;
    }while (ok==0 && k<=n+1);
    if (ok==0)
    {
        fout<<"Ciclu negativ!";
    }
    else
    {
        for (i=2;i<=n;i++)
        {
            fout<<d[i]<<" ";
        }
    }
    fout.close();
    fin.close();
    return 0;
}