#include <iostream>
#include<fstream>
#include<queue>
#include<vector>
#define pb push_back
using namespace std;
int d[50001],i,j,n,k,c,X,m,l,N[50001];
bool u[50001];
struct nod
{
    int x,c,p;
}x;
vector<nod >a[50001];
queue<int>q;
int BF(int k)
{
  //  for(ok=1,nr=1;ok&&nr<n;++nr)
    //{
        //ok=0;
        q.push(1);
        u[1]=1;
        while(!q.empty())
        {
            i=q.front();
            q.pop();
            u[i]=1;
            for(l=0;l<N[i];++l)
            {
                j=a[i][l].x;
                c=a[i][l].c;
                ++a[i][l].p;
                if(d[j]>d[i]+c)
                {
                    d[j]=d[i]+c;
                   // ok=1;
                    //if(!u[j])
                        q.push(j);
                    if(a[i][l].p>n-3)return 1;
                }

            }
        }
       // for(i=0;i<n;++i)u[i+1]=0;

    //}
    return 0;
}
int main()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>X>>x.x>>x.c;
        x.p=0;
        a[X].pb(x);
        ++N[X];
    }
    f.close();
    for(i=1;i<n;++i)d[i+1]=1e8;
    d[1]=0;
    ofstream g("bellmanford.out");
    if(BF(1))
    {
        g<<"Ciclu negativ!";
    }
    else
    {
        for(i=1;i<n;++i)
            g<<d[i+1]<<" ";
    }
    return 0;
}