#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int N = 5e4+5;
const int oo = 0x3f3f3f3f;

int n, cost[N], cnt[N];
vector<pii> e[N];

void read(), bellmanford();

int main()
{
    read();
    bellmanford();
    for (int i = 2; i <= n; i++) g << cost[i] << ' ';

    return 0;
}

void read()
{
    int m;
    f >> n >> m;
    while (m--){
        int a, b, c; f >> a >> b >> c;
        e[a].pb({b, c});
    }   
    memset(cost, oo, sizeof cost);
}
void bellmanford(){
    queue<pii> q; q.push({1,0}); cost[1] = 0;
    while (!q.empty()){
        int from, c; tie(from, c) = q.front(); q.pop();
        for (auto it: e[from]){
            int to, cm; tie(to, cm) = it;
            if (cm + c < cost[to]){
                cost[to] = c + cm; 
                cnt[to]++;
                if (cnt[to] == n + 2){
                    g << "Ciclu negativ!";
                    exit(0);
                }
                q.push({to, cost[to]});
            }
        }
    }
}