#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

#define inf 0x3f3f3f3f
#define MAXN 50005

using namespace std;

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

int N, M, cost[MAXN], cnt[MAXN];

struct str{
    int node, c;
};

vector <str> graph[MAXN];
queue <int> Q;

inline void Read() {
    int x, y, z;

    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        fin >> x >> y >> z;

        graph[x].push_back({y, z});
    }
}

inline void BellmanFord(int start) {
    int z;

    memset(cost, inf, sizeof(cost));
    cost[start] = 0; cnt[start] = 1;
    Q.push(start);

    while (!Q.empty()) {
        z = Q.front();

        if (cnt[z] > N - 1) {
            fout << "Ciclu negativ!\n";
                return;
        }

        for (auto x : graph[z]) {
            if (cost[x.node] > cost[z] + x.c) {
                cost[x.node] = cost[z] + x.c;

                Q.push(x.node);
            }
        }

        Q.pop();
    }

    for (int i = 2; i <= N; i++) {
        fout << cost[i] << " ";
    }
}

int main () {
    Read();
    BellmanFord(1);

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