#include <bits/stdc++.h>
#define oo 1e9
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
vector <pair <int,int> > L[200001];
int x,y,c,n,m,k,v;
int d[200001],viz[200001],contor[200001];
queue <int> q;
void citire ()
{
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
}
void BellmanFord ()
{
    bool existanegative=false;
    //initializari
    for (int i=2; i<=n; i++)
        d[i]=oo;
    viz[1]=1;
    q.push(1);
    contor[1]=1;
    while (!q.empty() && !existanegative)
    {
        k=q.front();
        q.pop();
        viz[k]=0;
        for (int j=0; j<L[k].size(); j++)
        {
            v=L[k][j].first;
            c=L[k][j].second;
            if(d[k]+c<d[v])
            {
                d[v]=d[k]+c;
                if (viz[v]==0)
                    if (contor[v]>n)existanegative=true;
                    else
                    {
                        q.push(v);
                        viz[v]=1;
                        contor[v]++;
                    }
            }
        }
    }
    if (existanegative)
        fout<<"ciclu negativ";
    else
        for (int p=1; p<=n; p++)
            fout<<d[p]<<" ";
}
int main()
{
    citire ();
    BellmanFord();
    return 0;
}