#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct Muchie {
    int to;
    int cost;
};

vector <Muchie> g[50005];
queue <int> q;
int sol[50005], apar[50005];

int bfs(int n) {
    q.push(1);

    while(!q.empty()) {
        int u = q.front();
        ++ apar[u];
        if(apar[u] == n + 1) {
            return 0;
        }

        for(int k = 0; k < g[u].size(); ++ k) {
            int v = g[u][k].to, c = g[u][k].cost;

            if(sol[u] + c < sol[v]) {
                q.push(v);
                sol[v] = sol[u] + c;
            }
        }

        q.pop();
    }

    return 1;
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++ i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        g[u].push_back({v, c});
    }

    for(int i = 2; i <= n; ++ i) {
        sol[i] = 2000000000;
    }

    if(bfs(n) != 1) {
        printf("Ciclu negativ!");
        return 0;
    }

    for(int i = 2; i <= n; ++ i) {
        printf("%d ", sol[i]);
    }

    return 0;
}