#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 50005;
vector<pair<int, int>> G[kMaxN];
long long Dist[kMaxN];
bool In[kMaxN];

void DFS(int node) {
    In[node] = true;
    for (auto e : G[node]) {
        int vec, cost; tie(vec, cost) = e;

        if (Dist[vec] <= Dist[node] + cost) continue;
        
        if (In[vec]) throw 5;
        Dist[vec] = Dist[node] + cost;
        DFS(vec);
    }
    In[node] = false;
}

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

    int n, m; cin >> n >> m;
    memset(Dist, 0x3f, sizeof(Dist));
        
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        G[a - 1].emplace_back(b - 1, c);
    }

    for (int i = 0; i < n; ++i) {
        sort(G[i].begin(), G[i].end(), [](pair<int, int> a, pair<int, int> b) {
            return a.second < b.second;
        });
    }
    Dist[0] = 0;
    try { DFS(0); } catch (int) {
        cout << "Ciclu negativ!" << endl;
        return 0;
    }

    for (int i = 1; i < n; ++i) {
        cout << Dist[i] << " ";
    }
    cout << endl;
    
    return 0;
}