#include <bits/stdc++.h>

#define bufs 1000000
#define nxt() {pos++;\
    if(pos >= bufs)\
    {\
        fread(buf, 1, bufs, stdin);\
        pos = 0;\
    }\
}

using namespace std;

char buf[bufs];
int pos = bufs;
int neg;

inline void read(int& val)
{
    neg = 0;
    while((buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') nxt();
    if(buf[pos] == '-') { neg = 1; val = 0; }
    else val = buf[pos] - '0';
    nxt();
    while(buf[pos] >= '0' && buf[pos] <= '9') { val = val * 10 + buf[pos] - '0'; nxt(); }
    if(neg == 1) val = -val;
}

struct Muchie {
    int v, c;

    bool operator<(const Muchie& m) const {
        return c > m.c;
    }
};

vector<Muchie> g[50010];
int viz[50010];
int dist[50010];
int n, m;

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    read(n); read(m);
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        read(a); read(b); read(c);
        g[a].push_back({b, c});
    }
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<Muchie> q;
    q.push({1, 0});
    viz[1] = 1;
    dist[1] = 0;
    while(!q.empty())
    {
        int nod = q.top().v;
        int cost = q.top().c;
        q.pop();

        if(cost > dist[nod])
            continue;

        viz[nod]++;
        if(viz[nod] >= n)
        {
            printf("Ciclu negativ!");
            return 0;
        }

        for(const auto& vec : g[nod])
        {
            if(dist[nod] + vec.c < dist[vec.v])
            {
                dist[vec.v] = dist[nod] + vec.c;
                q.push({vec.v, dist[vec.v]});
            }
        }
    }
    for(int i = 2; i <= n; i++)
        printf("%d ", dist[i]);
    return 0;
}