#include <fstream>

using namespace std;

struct il
{
    int l,c,cost;
};
il a[250001];
int n,m,v[50001],x,y,cost,i,j;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
bool ok;
int main()
{
    f>>n>>m;
    for (i=1; i<=n; i++)
        v[i]=1<<31-1;
    v[1]=0;
    for (i=1; i<=m; i++)
        f>>x>>y>>cost,
        a[i].l=x,a[i].c=y,a[i].cost=cost;
    for (i=1; i<=n-1; i++)
    {
        for (j=1; j<=m; j++)
            if (v[a[j].l]+a[j].cost<v[a[j].c])
                v[a[j].c]=v[a[j].l]+a[j].cost;
    }
    ok=true;
    for(j=1;j<=m;j++)
    if (v[a[j].l]+a[j].cost<v[a[j].c])
        ok=false;
    if (ok==false) g<<"Ciclu negativ!";
    else
    for (i=2;i<=n;i++)
    g<<v[i]<<' ';
    return 0;
}