#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define DIM 50002
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int nodes,edges,negative_cycle;
vector < pair <int,int > > v[DIM];
queue <int> Q;
bitset <DIM> inQueue;
int cnt_inQueue[DIM];
vector <int> dist(DIM,INF);
int main(){
    fin>>nodes>>edges;
    while( edges-- ){
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    dist[1]=0;
    inQueue[1]=true;
    Q.push(1);
    while(!Q.empty() && !negative_cycle){
        int node=Q.front();
        inQueue[node]=false;
        Q.pop();
        for(std::vector <pair <int ,int > >::iterator it=v[node].begin();it!=v[node].end();it++){
            if(dist[it->first] > dist[node]+it->second){
                dist[it->first] = dist[node]+it->second;
                if(!inQueue[it->first]){
                    if(cnt_inQueue[it->first] > nodes)
                        negative_cycle=true;
                    else{
                        Q.push(it->first);
                        inQueue[it->first]=true;
                        cnt_inQueue[it->first]++;
                    }
                }
            }
        }
    }
    if(negative_cycle==true)
        fout<<"Ciclu negativ!";
    else{
        for(int i=2;i<=nodes;i++)
            fout<<dist[i]<<" ";
    }
    fin.close();fout.close();
    return 0;
}