#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int MAXN = 1 * 1e5 + 5;
const int INF = 1e8;
struct edge{
    int dest, cost;
};
vector <edge> g[MAXN];
int dist[MAXN], cnt[MAXN];
queue <edge> coada;
bool ok = true;
void bfs(int start, int n){
    coada.push({start, 0});
    while(coada.size() and ok){
        int node = coada.front().dest;
        int c = coada.front().cost;
        cnt[node]++;
        if(cnt[node] == n) ok = false;
        coada.pop();
        if(dist[node] >= c){
            dist[node] = c;
            for(auto x: g[node]){
                if(dist[x.dest] > dist[node] + x.cost){
                    dist[x.dest] = dist[node] + x.cost;
                    coada.push({x.dest, dist[x.dest]});
                }
            }
        }
    }
}
int main()
{
    int n, m; fin >> n >> m;
    for(int i = 1; i <= n; ++i)
        dist[i] = INF;
    for(int i = 1;i <= m; ++i){
        int x, y, c; fin >> x >> y >> c;
        g[x].push_back({y, c});
    }
    bfs(1, n);
    if(!ok) fout << "Ciclu negativ!";
    else{
        for(int i = 2; i <= n; ++i)
            fout << dist[i] << " ";
    }
    return 0;
}