#include <fstream>
#include <climits>
#include <vector>
#include <queue>

#define MAXN 50002

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct two{
    int nod, c;
};

vector <two> G[MAXN];
queue <int> Q;

int n, m, cost[MAXN], x, y, cc, fr[MAXN], z;
bool poz[MAXN];

inline void Read() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> cc;
        G[x].push_back({y, cc});
    }
}

inline void Init() {
    for (int i = 1; i <= n; i++)
        cost[i] = INT_MAX,
        fr[i] = 0,
        poz[i] = 0;
}

inline int Bellman_Ford(int start) {
    cost[start] = 0; Q.push(start);

    while (!Q.empty()) {
        z = Q.front(); poz[z] = 0;

        for (vector <two> :: iterator i = G[z].begin(); i != G[z].end(); i++) {
            if (cost[(*i).nod] > cost[z] + (*i).c) {
                cost[(*i).nod] = cost[z] + (*i).c;

                if (!poz[(*i).nod]) {
                    poz[(*i).nod] = 1;
                    Q.push((*i).nod);
                    fr[(*i).nod]++;

                    if (fr[(*i).nod] == m)
                        return 0;
                }
            }
        }

        Q.pop();
    }

    return 1;
}

inline void Solve() {
    Init();
    if (Bellman_Ford(1)) {
        for (int i = 2; i <= n; i++) {
            fout << cost[i] << " ";
        }
    }
    else
        fout << "Ciclu negativ!\n";
}

int main () {
    Read();
    Solve();

    fin.close(); fout.close(); return 0;
}