#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define inf 999999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct Nod
{
    vector<int>ad;
    vector<int>cost;
} graf[50002];

int n,m;
int dist[50002];
int count_q[50002];///de cate ori a fost adaugat nodul in coada
bool in_q[50002];///daca nodul se afla in coada
bool ciclu;

void Citire()
{
    fin>>n>>m;
    int i,j,c,x,y;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        graf[x].ad.push_back(y);
        graf[x].cost.push_back(c);
    }
}
void Bellman()
{
    for(int i=2;i<=n;i++)
        dist[i]=inf;
    deque<int>Q;
    int nc;///nod curent
    int w,c;
    Q.push_back(1);
    while(!Q.empty()&&!ciclu)
    {
        nc=Q.front();
        Q.pop_front();

        in_q[nc]=0;

        for(int i=0;i<graf[nc].ad.size();i++)
        {
            w=graf[nc].ad[i];
            c=graf[nc].cost[i];

            if(dist[w]>dist[nc]+c)
            {
                dist[w]=dist[nc]+c;
                if( !in_q[w] )
                    if(count_q[w]>n)
                    {
                        ciclu=1;
                        break;
                    }
                    else
                    {
                        in_q[w]=1;
                        ++count_q[w];
                        Q.push_back(w);
                    }
            }
        }
    }
}
void Afisare()
{
    if(ciclu)
        fout<<"Ciclu negativ!"<<'\n';
    else
    {
        for(int i=2;i<=n;i++)
            fout<<dist[i]<<" ";
        fout<<'\n';
    }
}
int main()
{
    Citire();
    Bellman();
    Afisare();
    return 0;
}