#include <bits/stdc++.h>

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int NMAX=50005;
int n,m,dist[NMAX],cnt[NMAX];
bool in_q[NMAX];
struct edge{
    int node,cost;
};
vector<edge>g[NMAX];
queue<int>q;
int main()
{
    in>>n>>m;
    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    for(int i=1,a,b,cost;i<=m;i++){
        in>>a>>b>>cost;
        g[a].push_back({b,cost});
    }
    q.push(1);
    dist[1]=0;
    cnt[1]=1;
    while(!q.empty()){
        int node=q.front(),cost=dist[node];
        in_q[node]=0;
        q.pop();
        for(auto y:g[node]){
            if(dist[y.node]>cost+y.cost){
                dist[y.node]=cost+y.cost;
                cnt[y.node]++;
                if(cnt[node]>=n){
                    out<<"Ciclu negativ!";
                    return 0;
                }
                if(!in_q[y.node])
                q.push(y.node);
            }
        }
    }
    for(int i=2;i<=n;i++)
        out<<dist[i]<<" ";
    return 0;
}