#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m;
struct muchie{
  int vecin;
  int cost;
  int fr;
};
const int inf=2000000005;
vector <vector<muchie>>G;
vector <int> dist;
queue <int> coada;
void citire()
{
    fin>>n>>m;
    int x,y,cost;
    G.resize(n+1);
    dist.resize(n+1);
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>cost;
        G[x].push_back({y,cost,0});
    }
    for(int i=2;i<=n;i++)
    {
        dist[i]=inf;
    }
    coada.push(1);
    while(!coada.empty())
    {
        int nodcurent=coada.front();
        coada.pop();
        for(int i=0;i<G[nodcurent].size();i++)
        {
            int vecin=G[nodcurent][i].vecin;
            int upcost=G[nodcurent][i].cost+dist[nodcurent];
            if(upcost<dist[vecin])
            {
                if(G[nodcurent][i].fr==n-1)
                {
                    fout<<"Ciclu negativ!";
                    return;
                }
                dist[vecin]=upcost;
                G[nodcurent][i].fr++;
                coada.push(vecin);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        fout<<dist[i]<<" ";
    }
}
int main()
{
    citire();
    return 0;
}