//thanks to Marius Stroe
#include <fstream>
#include <utility>
#include <vector>
#include <list>
#include <queue>
#include <limits>

const int INFINT=std::numeric_limits<int>::max();
typedef std::pair<unsigned,int> PUI_t;

int main(){
    std::ifstream fin("bellmanford.in");
    std::ofstream fout("bellmanford.out");

    unsigned n,m;
    fin>>n>>m;

    std::vector< std::list<PUI_t> > Adj(n+1);
    for(unsigned i=0;i<m;++i){
        unsigned x,y; int c;
        fin>>x>>y>>c;
        Adj[x].push_back(PUI_t(y,c));
    }

    std::vector<int> dist(n+1,INFINT);
    std::vector<unsigned> cnt_queued(n+1,0);
    std::queue<unsigned> active;
    std::vector<bool> enqueued(n+1,false);

    dist[1]=0; active.push(1); enqueued[1]=true;
    bool ciclu_negativ=false;
    while(!active.empty() && !ciclu_negativ){
        unsigned v=active.front();
        active.pop(); enqueued[v]=false;

        for(auto it=Adj[v].begin(); it!=Adj[v].end(); ++it)
            if( dist[it->first] > ( dist[v] + it->second ) ){
                dist[it->first] = dist[v]+it->second;
                if(!enqueued[it->first]){
                    if(cnt_queued[it->first]>=n){
                        ciclu_negativ=true;
                    }
                    else{
                        active.push(it->first);
                        enqueued[it->first]=true;
                        cnt_queued[it->first]++;
                    }

                }
            }
    }

    if(ciclu_negativ) fout<<"Ciclu negativ!\n";
    else{
        for(unsigned i=2;i<=n;++i) fout<<dist[i]<<' ';
        fout<<'\n';
    }
}