#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;
}

void Read(int& x) {
    static char c;
    
    for (c = getchar(); !isdigit(c) && c != '-'; c = getchar());
    
    bool sgn = 0;
    if (c == '-') { sgn = 1; c = getchar(); }

    for (x = 0; isdigit(c); c = getchar())
        x = (x << 1) + (x << 3) + c - '0';
    
    if (sgn) x = -x;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m; Read(n); Read(m);
    memset(Dist, 0x3f, sizeof(Dist));
        
    while (m--) {
        int a, b, c; Read(a); Read(b); Read(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;
}