#include<fstream>
#include<vector>
#include<deque>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int NMax=50005;
const int INF=1e9;
struct muchie
{
    int node,cost;
};
vector<muchie>v[NMax];
deque<int>Q;
int cot[NMax],dist[NMax],n;
bool ciclu=false;
muchie make_muchie(const int &a,const int &b)
{
    muchie rez;
    rez.node=a;
    rez.cost=b;
    return rez;
}
void bellman(const int &start_node)
{
    int nod;
    Q.push_back(start_node);
    for(int i=0;i<=n;i++)
      dist[i]=INF;
    dist[1]=0;
    while(!Q.empty())
    {
        nod=Q.front();
        Q.pop_front();
        for(int i=0;i<v[nod].size()&&ciclu==false;i++)
        {
            if(dist[v[nod][i].node]>dist[nod]+v[nod][i].cost)
            {
                dist[v[nod][i].node]=dist[nod]+v[nod][i].cost;
                Q.push_back(v[nod][i].node);
                cot[v[nod][i].node]++;
                if(cot[v[nod][i].node]>n)
                {
                    ciclu=true;
                }
            }
        }
    }
}
int main()
{
    int m,a,b,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].push_back(make_muchie(b,c));
    }
    bellman(1);
    if(ciclu==false)
    {
        for(int i=2;i<=n;i++)
        {
            fout<<dist[i]<<" ";
        }
        fout<<"\n";
    }
    else
    {
        fout<<"Ciclu negativ!"<<"\n";
    }
    return 0;
}