#include <bits/stdc++.h>

using namespace std;

#define INFILE "bellmanford.in"
#define OUTFILE "bellmanford.out"

const int N_MAX = 50000;
const int INF = 0x3f3f3f3f;

struct Node {

    int node;
    int cost;

    Node(){}
    Node(int _node, int _cost) : node(_node), cost(_cost) {}

};

int n, m;
vector<Node> adj[N_MAX + 5];

queue<int> q;
bool negativeCycle;
bool inQueue[N_MAX + 5];
int cntQueue[N_MAX + 5];

int dist[N_MAX + 5];

void relax(int node, int cost){
    if(cost < dist[node]){
        dist[node] = cost;
        if(!inQueue[node]){
            q.push(node);
            inQueue[node] = true;
            ++cntQueue[node];
            if(cntQueue[node] == n) negativeCycle = true;
        }
    }
}

void solve(){

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int node, to, cost; cin >> node >> to >> cost;
        adj[node].push_back(Node(to, cost));
    }

    memset(dist, INF, sizeof dist);
    
    dist[1] = 0;
    q.push(1);
    inQueue[1] = true;
    cntQueue[1] = n -1;

    while(!q.empty() && !negativeCycle){

        int node = q.front(); q.pop();
        inQueue[node] = false;

        for(auto &to : adj[node]){
            relax(to.node, dist[node] + to.cost);
        }

    }

    if(negativeCycle) cout << "Ciclu negativ!" << '\n';
    else {
        for(int i = 2; i <= n; ++i){
            cout << dist[i] << " ";
        }
        cout << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    solve();
    return 0;
}