#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ll;
typedef pair < int , int > PII;
typedef pair < int , PII >  PIPII;

int n, m, dist[50100];

struct cmp{
    bool operator()(int a, int b){
        return dist[a] > dist[b];
    }
};


priority_queue < int, vector < int >, cmp > H;
vector < PII > V[50100];
bitset < 50100 > insideH;

void Bellman(int src){
    H.push(src);
    int pas = 0;
    
    while (H.size() && pas <= n * m){
        int x = H.top(); H.pop();
        insideH[x] = 0;
         
        for (auto it : V[x]){
            if (dist[it.first] > dist[x] + it.second){
                dist[it.first] = dist[x] + it.second;
                if (insideH[it.first] == 0){
                    H.push(it.first);
                    insideH[it.first] = 1;
                }
            }
        }
    }
}

bool checker(istream& cin){
    cin.seekg(0, cin.beg);
    cin >> n >> m;
    for (int i = 1, x, y, c; i <= m; i++){
        cin >> x >> y >> c;
        if (dist[x] + c < dist[y])
            return 1;
    }
    
    return 0;
}

int main(){
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x, y, c; i <= m; i++){
        cin >> x >> y >> c;
        V[x].push_back({y, c});
    }

    for (int i = 2; i <= n; i++) dist[i] = 2e9;

    Bellman(1);
    if (checker(cin)) return cout << "Ciclu negativ!", 0;

    for (int i = 2; i <= n; i++)
        cout << (dist[i] == 2e9 ? 0 : dist[i]) << " ";
    return 0;
}