#include <fstream>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int m,n,d[50010],okf,muc[250010][3];
void bellman (int sursa)
{
    int i,j,a,b,c,ok;
    d[sursa]=0;
    for (ok=i=1;ok&&i<n;i++)
        for (j=1,ok=0;j<=m;j++)
        {
            a=muc[j][0];
            b=muc[j][1];
            c=muc[j][2];
            if (d[b]>d[a]+c)
            {
                d[b]=d[a]+c;
                ok=1;
            }
        }
    for (i=1;i<=m;i++)
    {
        a=muc[i][0];
        b=muc[i][1];
        c=muc[i][2];
        if (d[b]>d[a]+c)
        {
            okf=1;
            return;
        }
    }
}
int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>muc[i][0]>>muc[i][1]>>muc[i][2];
    fin.close ();
    for (i=1;i<=n;i++)
        d[i]=2000000000;
    bellman (1);
    if (okf)
        fout<<"Ciclu negativ!\n";
    else
        for (i=2;i<=n;i++)
            fout<<d[i]<<' ';
    fout<<'\n';
    fout.close ();
    return 0;
}