#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
# define inf 1<<30
using namespace std;

struct nod
{
    int x, c;
};
vector <nod> vec[50010];
queue <int> Q;
int viz[50010],cnt[50010],dmin[50010],n,m;

void citire()
{
    freopen("bellmanford.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int k;
        nod u;
        scanf("%d %d %d",&k,&u.x,&u.c);
        vec[k].push_back(u);
    }
}
int ok=0;
void bellmanford()
{
    for(int i=2;i<=n;i++)
        dmin[i]=inf;

    viz[1]=1;
    cnt[1]++;
    Q.push(1);
    while(!Q.empty() && !ok)
    {
        int vf=Q.front();
        Q.pop();
        viz[vf]=0;
        for(int i=0;i<vec[vf].size() && !ok;i++)
        {
            nod u=vec[vf][i];

            if(dmin[vf]+u.c<dmin[u.x])
            {
                dmin[u.x]=dmin[vf]+u.c;
                cnt[u.x]++;
                if(cnt[u.x]>n)
                    ok=1;
                if(!viz[u.x])
                {
                    Q.push(u.x);
                    viz[u.x]=1;
                }
            }

        }
    }

}

void afisare()
{
    freopen("bellmanford.out", "w", stdout);
    if(ok)
        cout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            cout<<dmin[i]<<" ";
}


int main()
{
    citire();
    bellmanford();
    afisare();
    return 0;
}