#include <bits/stdc++.h>
#define oo 1e9

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n,m,dist[50005],frecv[50005];
bitset<50005>viz;
vector<pair<int,int> >L[250005];
queue<int>q;

void Citire()
{
    int x,y,c;
    fin>>n>>m;

    while(m--)
    {
        fin>>x>>y>>c;
        L[x].push_back({y,c});
    }

    for(int i=1;i<=n;i++)
        dist[i]=oo;
}

void Rezolva()
{
    int ciclu;
    ciclu=0;

    viz[1]=1;
    dist[1]=0;
    q.push(1);
    frecv[1]=1;

    while(!q.empty() && !ciclu)
    {
        int x=q.front();
        q.pop();
        viz[x]=0;

        for(auto i:L[x])
            if(dist[i.first]>dist[x]+i.second)
            {
                dist[i.first]=dist[x]+i.second;
                if(!viz[i.first])
                {
                    viz[i.first]=1;
                    frecv[i.first]++;
                    if(frecv[i.first]>n)
                        ciclu=1;
                    q.push(i.first);
                }
            }
    }

    if(ciclu)fout<<"Ciclu negativ!\n";
    else
    {
        for(int i=2;i<=n;i++)
            fout<<dist[i]<<" ";

        fout<<"\n";
    }
}

int main()
{
    Citire();
    Rezolva();

    fin.close();
    fout.close();
    return 0;
}