#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#include <climits>

using namespace std;

struct Muchie{
    int c,x,y;
};

int viz[100001];
vector <Muchie> M;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int d[100001];

//dijkstra
//void Dijkstra(){
//    while(!pq.empty()){
//        int nod=pq.top().second;
//
//        pq.pop();
//        if(viz[nod]){
//            continue;
//        }
//
//        viz[nod]=1;
//
//        for(auto m: M){
//            if(m.x==nod){
//                int y=m.y;
//                int cost=m.c;
//                if(d[nod]+cost<d[y]){
//                    d[y]=d[nod]+cost;
//                    pq.push({cost,y});
//                }
//
//            }
//        }
//
//
//    }
//}
//
//
//int main(){
//
//    ifstream cin("dijkstra.in");
//    ofstream cout("dijkstra.out");
//
//    int n,m;
//    cin>>n>>m;
//
//    for(int i=1; i<=n; i++){
//        d[i]=INT_MAX;
//    }
//
//    d[1]=0;
//
//    for(int i=0; i<m; i++){
//        int x,y,c;
//        cin>>x>>y>>c;
//        M.push_back({c,x,y});
//    }
//
//    pq.push({0,1});
//
//    Dijkstra();
//
//
//
//    return 0;
//}

//Bellman-Ford

void BellmanFord(int n){

    for(int i=0; i<n-1; i++){
        for(auto m: M){
            int x,y,c;
            x=m.x;
            y=m.y;
            c=m.c;
            if(d[x]+c<d[y]){
                d[y]=d[x]+c;
            }
        }
    }

}

int main(){
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");

    int n,m;
    cin>>n>>m;

    for(int i=0; i<m; i++){
        int x,y,c;
        cin>>x>>y>>c;
        M.push_back({c,x,y});
    }

    for(int i=1; i<=n; i++){
        d[i]=INT_MAX;
    }

    d[1]=0;

    BellmanFord(n);

    int ok=1;

    for(auto m: M){
        int x,y,c;
        x=m.x;
        y=m.y;
        c=m.c;
        if(d[x]!=INT_MAX && d[x]+c<d[y]){
            ok=0;
            break;
        }
    }

    if(!ok){
        cout<<"Ciclu negativ!";
    }
    else{
        for(int i=2; i<=n; i++){
            cout<<d[i]<<" ";
        }
    }


    return 0;
}