#include <bits/stdc++.h>

using namespace std;

const int N=5e4+5;

vector<pair<int, int>> adj[N];

int dist[N], vis[N];

int main()
{
    memset(dist, (1<<6)-1, sizeof(dist));
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for (int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v, w});
    }
    dist[1]=0;
    for (int i=1;i<n;i++){
        for (int u=1;u<=n;u++){
            for (auto [v, w]:adj[u]){
                if (dist[u]+w<dist[v]){
                    dist[v]=dist[u]+w;
                }
            }
        }
    }
    for (int u=1;u<=n;u++){
        for (auto [v, w]:adj[u]){
            if (dist[u]+w<dist[v]){
                cout<<"Ciclu negativ!";
                return 0;
            }
        }
    }
    for (int i=2;i<=n;i++){
        cout<<dist[i]<<' ';
    }
    return 0;
}