#include <bits/stdc++.h>

using namespace std;

const int N=5e4+5;

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

int dist[N], vis[N];

bool inqueue[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});
    }
    queue<int> q;
    dist[1]=0;
    q.push(1);
    inqueue[1]=true;
    while (!q.empty()){
        int node=q.front();q.pop();
        inqueue[node]=false;
        for (auto [newnode, weight]: adj[node]){
            if (dist[newnode]>dist[node]+weight){
                dist[newnode]=dist[node]+weight;
                if (!inqueue[newnode]){
                    q.push(newnode);
                    vis[newnode]++;
                    if (vis[newnode]==n){
                        cout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for (int i=2;i<=n;i++){
        cout<<dist[i]<<' ';
    }
    return 0;
}