#include <fstream>

using namespace std;

struct list{
    int u,v,c;
};

list l[250001];
int d[50001];

int main()
{   int i,j,n,m;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    d[1]=0;
    for(i=2;i<=n;i++) d[i]=2100000000;
    for(i=1;i<=m;i++)
    {
        f>>l[i].u>>l[i].v>>l[i].c;
    }

    for(i=1;i<=n-1;i++)
        for(j=1;j<=m;j++)
        {
            if(d[l[j].u]+l[j].c<d[l[j].v]) d[l[j].v]=d[l[j].u]+l[j].c;
        }
    for(j=1;j<=m;j++)
        if(d[l[j].u]+l[j].c<d[l[j].v])
        {
            g<<"Ciclu negativ!\n";
            return 0;
        }
    for(i=2;i<=n;i++) g<<d[i]<<' ';
    g<<'\n';


    f.close();
    g.close();
    return 0;
}