#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int NMAX = 50000 + 5;
int n,m,nr[NMAX],sol[NMAX];
bool in[NMAX];
vector < pair<int,int> > g[NMAX];
int main() {
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d %d\n", &n, &m);
    for (int i = 1; i<=n; ++i)
        sol[i] = INT_MAX;
    for (int i = 1; i<=m; ++i) {
        int x,y,c;
        scanf("%d %d %d\n", &x, &y, &c);
        g[x].push_back({y,c});
    }

    queue <int> q;
    q.push(1);
    nr[1] = 1;
    sol[1] = 0;
    while(!q.empty()) {
        int cap = q.front();
        in[cap] = false;
        for (auto &it : g[cap])
            if (sol[it.f] > sol[cap] + it.s) {
                sol[it.f] = sol[cap] + it.s;
                if (in[it.f] == false) {
                    in[it.f] = true , q.push(it.f);
                }
                ++nr[it.f];
                if (nr[it.f] > n) {
                    printf("Ciclu negativ!");
                    return 0;
                }

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

    return 0;
}