#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define dim 50005
#define int long long
const int INF=5e7+5;
struct muchie
{
    int y,c;
};
vector<muchie> v[dim];
vector<int> dist;
bool ciclu;
int n;
void bellman(int nod)
{
    queue<int> q;
    vector<int> cnt(n+1,0);
    dist=vector<int>(n+1,INF);
    dist[nod]=0;
    q.push(nod);
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        for(auto [y,c]:v[nod])
        {
            if(dist[y]>dist[nod]+c)
            {
                dist[y]=dist[nod]+c;
                cnt[y]++;
                if(cnt[y]==n)
                {
                    ciclu=true;
                    return ;
                }
                q.push(y);
            }
        }
    }
}

signed main()
{
    int m,i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    ciclu=false;
    bellman(1);
    if(ciclu==true)
        fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            fout<<dist[i]<<" ";
    return 0;
}