#include <fstream>

#include <vector>

#include <queue>

using namespace std;

ifstream fin("bellmanford.in");

ofstream fout("bellmanford.out");

int n,m;

const int N=50002;

const int INF=250000000;

vector <pair<int,int>> a[N];

queue <int> q;

int nrq[N],d[N];

bool inq[N];

int main()

{

    fin>>n>>m;

    int x,y,c,i,j;

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

    {

        fin>>x>>y>>c;

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

    }

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

       d[i]=INF;

     q.push(1);

     d[1]=0;

     inq[1]=true;

     nrq[1]++;

     while(!q.empty()){

        x=q.front();

        q.pop();

        inq[x]=false;

        for(auto p : a[x]){

            y=p.first;

            c=p.second;

            if(d[x]+c<d[y]){

                d[y]=d[x]+c;

                if(!inq[y]){

                    q.push(y);

                    inq[y]=true;

                    nrq[y]++;

                    if(nrq[y]==n){

                        fout<<"Ciclu negativ!";

                        return 0;

                    }

                }

            }

        }

     }

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

      fout<<d[i]<<" ";

    return 0;

}