#include <fstream>
#include <queue>
#include <vector>
#define DIM 50002
#define INF 1e9
#define ff first
#define ss second

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m, viz[DIM], sol[DIM], F[DIM], x, y, c;

vector <pair<int, int> > graf[DIM];

queue <int> q;

bool bf(){
    for(int i = 2; i <= n; ++ i)
        sol[i] = INF;
    q.push(1);
    F[1] = 1;
    viz[1] = 1;
    while(!q.empty()){
        int nodc = q.front();
        for(int i = 0; i < graf[nodc].size(); ++ i){
            int nodv = graf[nodc][i].ff;
            int cost = graf[nodc][i].ss;
            if(sol[nodc] + cost < sol[nodv]){
                sol[nodv] = sol[nodc] + cost;
                ++ F[nodv];
                if(F[nodv] == n)
                    return 1;
                if(!viz[nodv]){
                    q.push(nodv);
                    viz[nodv] = 1;
                }
            }
        }
        q.pop();
        viz[nodc] = 0;
    }
    return 0;
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; ++ i){
        f>>x>>y>>c;
        graf[x].push_back(make_pair(y, c));
    }
    if(bf()){
        g<<"Ciclu negativ!";
        return 0;
    }
    for(int i = 2; i <= n; ++ i)
        g<<sol[i]<<" ";
    return 0;
}