#include <iostream>
#include<fstream>
#include <vector>
#include <queue>
#define Nmax 50005
#define inf 1000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<pair <int,int> >G[Nmax];
queue<int>Q;
int n,m,D[Nmax],Nr[Nmax];
bool InQ[Nmax],ok;

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

}

void afisare()
{
    if(ok)
      fout<<"Ciclu negativ!";
      else
          for(int i=2;i<=n;i++)
                 fout<<D[i]<<" ";

}
void start()
{
    for(int i=2;i<=n;i++)
        D[i]=inf;
     D[1]=0;
     Nr[1]=1;
     Q.push(1);
     InQ[1]=true;
}

void Bellman_Ford(int a)
{

    for(start();!Q.empty();Q.pop())
    {
        int x=Q.front();
        InQ[x]=false;
        for(unsigned i=0;i<G[x].size();i++)
        {
            int vecin=G[x][i].first;
            int cost=G[x][i].second;

            if(D[x]+cost<D[vecin])
            {
                D[vecin]=D[x]+cost;
                if(!InQ[vecin])
                {
                    Q.push(vecin);
                    InQ[vecin]=true;
                }
                ++Nr[vecin];
                if (Nr[vecin]>=n)
                {
                    ok=true;
                     return;
                }


            }
        }
    }
}
int main()
{
    Read();
    Bellman_Ford(1);
    afisare();
    return 0;
}