#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <queue>
//#include <pair>
#define NMAX 50002
#define INF 100000
using namespace std;
//                      BELMAN FORD
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector< pair<int,int> > muchii[NMAX];//first = muchie second = cost
int cost[NMAX]={INF};
int freq[NMAX]={0};
bool BelmanFord(int start,int n){
    queue<int> coada;
    coada.push(start);
    for(int i=1;i<=n;i++){
        cost[i]=INF;
        freq[i]=0;
    }
    cost[start]=0;
    freq[start]++;
    bool ciclu=false;
    while(!coada.empty() && !ciclu){
        int el = coada.front();
        coada.pop();
        for(vector< pair <int,int> >::iterator it=muchii[el].begin();it!=muchii[el].end();it++){
            if(cost[it->first] > cost[el] + it->second ){
                cost[it->first] = cost[el] + it->second;
                coada.push(it->first);
                freq[it->first]++;
                if(freq[it->first] > n + 1)   ciclu = true;

            }
        }
    }
    return ciclu;
}

void afisare(int start,int n){
    for(int i=1;i<=n;i++)
        if(i!=start){
            if(cost[i]==INF)
                g << 0 << " ";
            else
                g << cost[i] << " ";
        }
}

int main()
{
    int n,m,a,b,c;
    f >> n >> m;
    for(int i=0;i<m;i++){
        f >> a >> b >> c;
        muchii[a].push_back(make_pair(b,c));
    }
    bool ciclu = BelmanFord(1,n);
    if(ciclu) g << "Ciclu negativ!";
    else
        afisare(1,n);
    return 0;
}