using namespace std;
#include<fstream>
ifstream eu("bellmanford.in");
ofstream tu("bellmanford.out");
#include <vector>
#include <queue>
#define NMax 50005
#define oo 0x3f3f3f3f
vector<pair<int,int> >G[NMax];
int N,M,D[NMax],Nr[NMax];
queue<int>Q;
bool InQ[NMax],ok;
void Read()
{
	eu>>N>>M;
    while(M--)
    {
		int X,Y,C;
		eu>>X>>Y>>C;
        G[X].push_back(make_pair(Y,C));
    }
}
void Print()
{
    if(ok)
    {
        tu<<"Ciclu negativ!";
    }
    else
    {
        for(int i=2;i<=N;i++)
        {
            tu<<D[i]<<" ";
        }
        tu<<"\n";
    }
}
void Ini()
{
    for(int i=1;i<=N;++i)
        D[i]=oo;
	D[1]=0;
    InQ[1]=true;
    Nr[1]=1;
    Q.push(1);
}
void Bellman_Ford(int b)
{
    for(Ini();!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);
    Print();
    return 0;
}