#include <bits/stdc++.h>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int NMAX = 50000;
const int INF = 0x3f3f3f3f;

int n,m;
vector < pair < int , int > > G[NMAX + 1];
queue < int > q;
int dist[NMAX + 1];
int viz[NMAX + 1];
int ciclu[NMAX + 1];
bool ok;

void read(){
    fin >> n >> m;
    for(int i = 1;i<=m;++i){
        int x,y,c;
        fin >> x >> y >> c;
        G[x].push_back({y,c});
    }
}

void initializare(){
    for(int i = 1;i<=n;++i)
        dist[i] = INF;
    dist[1] = 0;
}


void bellman_ford(){
    q.push(1);
    while(!q.empty()){
        int nodc = q.front();
        q.pop();
        viz[nodc] = 0;
        for(auto nbr : G[nodc])
            if(dist[nbr.first] > dist[nodc] + nbr.second){
                dist[nbr.first] = dist[nodc] + nbr.second;
                if(viz[nbr.first] == 0){
                    viz[nbr.first] = 1;
                    q.push(nbr.first);
                    ciclu[nbr.first] ++;
                    if(ciclu[nbr.first] > n){
                        cout << "Ciclu negativ!";
                        ok = true;
                        return ;
                    }
                }
            }
    }
}

int main(){


    read();
    initializare();
    bellman_ford();
    if(!ok){
        for(int i = 1;i<n;++i)
            fout << dist[i + 1] << ' ';
    }
    return 0;
}