#include<fstream>

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

#define DN 50005

using namespace std;

ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");

int n,m,x,y,c,a[DN],b[DN],p,ad[DN];

vector<pair<int,int> >gr[DN];

queue<int >q;

void ve()

{

    int nod;

    q.push(1);

    b[1]++;

    a[1]=0;

    while(!q.empty())

    {

        nod=q.front();

        q.pop();

        ad[nod]=0;

        for(int i=0;i<gr[nod].size();i++)

        {

            int vecin=gr[nod][i].first;

            int cost=gr[nod][i].second;

            if(a[nod]+cost<a[vecin])

            {

                a[vecin]=a[nod]+cost;

                b[vecin]++;

                if(b[vecin]==n)

                {

                    fout<<"Ciclu negativ!";

                    p=1;

                    return;

                }

                if(ad[vecin]==0)

                {

                    q.push(vecin);

                    ad[vecin]=1;

                }

            }

        }



    }



}

int main()

{

    fin>>n>>m;

    for(int i=1;i<=m;i++)

    {

        fin>>x>>y>>c;

        gr[x].push_back(make_pair(y,c));

    }

    for(int i=1;i<=n;i++)

        a[i]=1000000000;

    ve();

    if(p==0)

        for(int i=2;i<=n;i++)

            fout<<a[i]<<' ';

}