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

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

const int MAX_N = 50000 + 5;
const int MAN_M = 250000 + 5;

vector<pair<int,int> > gr[MAX_N];
/// cost. nod
queue<int> q;
bool ciclu;
int fost[MAX_N];
int cost[MAX_N];
int n,m,x,y,c;
void citire();

int main()
{

    citire();
    q.push(1);
    cost[1] = 0;

    while(!q.empty() && ciclu == false){
        int nod = q.front();
        q.pop();
        for(auto i : gr[nod]){
            if(cost[nod] + i.second < cost[i.first]){
                q.push(i.first);
                cost[i.first] = cost[nod] + i.second;
                fost[i.first]++;
                if(fost[i.first] > n)
                    ciclu = true;
            }
        }
    }

    if(ciclu)
        fout<<"Ciclu negativ!";
    else for (int i = 2;i<=n; ++i)
            fout<<cost[i]<<" ";


    return 0;
}

void citire(){

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

    for(int i = 1; i<=n; ++i)
        cost[i] = INT_MAX - 10000;

}