#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 > codi;
int dist[NMAX + 1];
int viz[NMAX + 1];
int ciclu[NMAX + 1];
bool ok = false;

void citire()
{
    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 init()
{
    for(int i = 1;i<=n;++i)
        dist[i] = INF;
    dist[1] = 0;
}


void BF()
{
    codi.push(1);
    while(!codi.empty()){
        int nodc = codi.front();
        codi.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;
                    codi.push(nbr.first);
                    ciclu[nbr.first] ++;
                    if(ciclu[nbr.first] > n){
                        fout << "Ciclu negativ!";
                        ok = 1;
                        return ;
                    }
                }
            }
    }
}

int main()
{
    citire();
    init();
    BF();
    if(ok==0)
    {
        for(int i = 1;i<n;++i)
            fout << dist[i + 1] << ' ';
    }
    return 0;
}