#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int inf=1<<30;

bool bellmanford(int n,int m,int start,vector<vector<pair<int,int> > >&adj,vector<int>&dist)
{
    dist[start]=0;
    queue<int>q;
    q.push(start);
    bool negativcycles=false;
    vector<bool>in_queue(n+1,false);
    vector<int>cnt(n+1);
    while(!negativcycles && !q.empty())
    {
        int x=q.front();
        q.pop();
        in_queue[x]=false;
        for(auto p:adj[x])
        {
            if(dist[x]<inf)
            {
                int edge=p.second;
                int v=p.first;
                if(dist[edge]>dist[x]+v)
                {
                    dist[edge]=dist[x]+v;
                    if(!in_queue[edge])
                    {
                        if(!cnt[edge]>n)
                            negativcycles=true;
                        else
                        {
                            q.push(edge);
                            in_queue[edge]=true;
                            cnt[edge]++;
                        }
                    }
                }
            }
        }
    }
    if(negativcycles){
        cout<<"ciclu negativ"<<'\n';
        return false;
    }
    return true;

}

int main()
{
    ifstream be("bellmanford.in");
    ofstream ki("bellmanford.out");
    int n,m;
    be>>n>>m;
    vector<vector<pair<int,int> > >adj(n+1);
    for(int i=0;i<m;i++)
    {
        int x,y,cost;
        be>>x>>y>>cost;
        adj[x].push_back({cost,y});
    }
    vector<int>dist(n+1,inf);
    auto c=bellmanford(n,m,1,adj,dist);
    if(c){
        for(int i=2;i<=n;i++)
        {
            ki<<dist[i]<<" ";
        }
        ki<<endl;
    }
    else ki<<"ciclu negativ"<<endl;
    return 0;

}