#include <bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
#define nmax 50101
#define pb push_back
#define inf 1e9
using namespace std;

ofstream fout("bellmanford.out");

typedef pair<int,int> p;

vector <p> v[nmax+1];

priority_queue <p,vector<p>,greater<p> > h;

int ans[nmax+1];
int n,m,i,a,b,c,nod;
int nr[nmax];

int main()
{
    FILE *fp;
    fp=fopen("bellmanford.in","r");
    fscanf(fp,"%d%d",&n,&m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fp,"%d%d%d",&a,&b,&c);
        v[a].pb(mp(c,b));
    }
    ans[1]=0;
    //fill(ans+2,ans+n+2,inf);
    for(i=2; i<=n; ++i)
        ans[i]=inf;
    h.push(mp(0,1));
    while(!h.empty())
    {
        nod=h.top().s;
        h.pop();
        nr[nod]++;
        if(nr[nod]>n)
        {
            fout<<"Ciclu negativ!";
            return 0;
        }
        for(i=0; i<v[nod].size(); ++i)
        {
            if(ans[nod]+v[nod][i].f<ans[v[nod][i].s])
            {
                ans[v[nod][i].s]=ans[nod]+v[nod][i].f;
                nr[v[nod][i].s]++;
                if(nr[v[nod][i].s]>n)
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                h.push(mp(ans[v[nod][i].s],v[nod][i].s));
            }
        }
    }
    for(i=2; i<=n; ++i)
    {
        if(ans[i]==inf)
            fout<<0<<" ";
        else fout<<ans[i]<<" ";
    }
    return 0;
}