#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);
    dist[1]=0;

    std::queue<unsigned> active;
    active.push(1);

    unsigned i=1;
    while(!active.empty() && i<n+1){
        ++i;
        active.push(0);
        unsigned v;
        while( (v=active.front()) !=0 ){
            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;
                    active.push(it->first);
                }
            active.pop();
        }
        active.pop();
    }

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