#include <iostream>
#include <bits/stdc++.h>

#define in_file "bellmanford.in"
#define out_file "bellmanford.out"
#define NMAX 50005
#define INF 0x3f3f3f

using namespace std;

vector<pair<int,int>> G[NMAX];
vector<int> usedtimes;
vector<int> dist;
priority_queue<pair<int,int>> q;

void printVec(vector<int> v){
    for(auto e : v){
        fprintf(stdout, "%d, ", e);
    }
}

void bf(int n, int s){
    dist[n]=0;
    usedtimes[n]++;
    q.push({0, n});
    while(!q.empty()){
        int curNode = q.top().second;
        int curLen = q.top().first;
        q.pop();
        for(auto n:G[curNode]){
            if(dist[n.first]>dist[curNode]+n.second){
                dist[n.first] = dist[curNode]+n.second;
                usedtimes[n.first]++;
                if(usedtimes[n.first]>s){
                    cout<<"Ciclu negativ!";
                    return;
                }
                q.push({curLen+1, n.first});
            }
        }
    }
    for(int i=2; i<=s;i++){
        cout<<dist[i]<<" ";
    }
}

int main()
{
    freopen(in_file, "r", stdin);
    freopen(out_file, "w", stdout);
    int n,m;
    int n1, n2, cost;
    cin>>n>>m;
    dist=vector<int>(n+1, INF);
    usedtimes=vector<int>(n+1, 0);
    while(m--){
        cin>>n1>>n2>>cost;
        G[n1].push_back({n2, cost});
    }
    bf(1, n);
    return 0;
}