#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#define lim 51000
using namespace std;
class Bellman
{
    int n,m,*fr,*dist,ok,nr;
    bool *incoada;
    queue<int> coada;
    struct muchie
    {
        int nod,cost;
    };
    vector<muchie> *vec;
    fstream in,out;
public:
    Bellman(int x,string fin,string fout)
    {
        in.open(fin.c_str(), ios::in);
        out.open(fout.c_str(), ios::out);
        nr=x;
        incoada = new bool[nr];
        fr = new int[nr];
        vec = new vector<muchie>[nr];
        dist = new int[nr];
    }
    ~Bellman()
    {
        delete[] incoada;
        delete[] fr;
        delete[] dist;
        delete[] vec;
        in.close();
        out.close();
    }
    void read()
    {

        int a;
        muchie b;
        in>>n>>m;
        //cout<<n<<" "<<m;
        for(int i=1;i<=m;i++)
        {
            //cout<<"ceva";
            in>>a>>b.nod>>b.cost;
            vec[a].push_back(b);
        }
    }
    int solve()
    {
        int x,y,i,cost;
        ok=1;
        while(ok && !coada.empty())
        {
            x = coada.front();
            coada.pop();
            incoada[x]=0;
            for(i=0;i<vec[x].size();i++)
            {
                y=vec[x][i].nod;
                cost=vec[x][i].cost;
                if(dist[x]+cost<dist[y])
                {
                    dist[y]=dist[x]+cost;
                    if(!incoada[y])
                    {
                        if(fr[y]>n)
                            ok=0;
                        else
                        {
                            coada.push(y);
                            incoada[y]=1;
                            fr[y]++;
                        }
                    }
                }
            }

        }
        if(ok==0)
            out<<"Ciclu negativ!"<<endl;
        else
        {
            for(i=2;i<=n;i++)
                out<<dist[i]<<" ";
        }
    }
    void init()
    {
        coada.push(1);
        incoada[1]=1;
        int i;
        for(i=1;i<=n;i++)
        {
            dist[i]=1<<30;
            fr[i]=0;
        }
        dist[1]=0;
    }
};
int main()
{
    Bellman X(lim,"bellmanford.in","bellmanford.out");
    X.read();
    X.init();
    X.solve();
    return 0;
}