#include <bits/stdc++.h>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

#define Nmax 50010
#define pb push_back
#define Mmax 250010

vector <int> T;
vector < pair <int,int> > v[Nmax];

int L[Mmax];
bool viz[Nmax];

int cmp(const int&a, const int &b)
{
    return L[a]>L[b];
}
inline void BF(){


   int node;
   T.pb(1);
   make_heap(T.begin(),T.end(),cmp);
   while(!T.empty()){

        node = T.front();
        pop_heap(T.begin(),T.end(),cmp);
        T.pop_back();
        for(int i=0;i<v[node].size();i++)
        {
                if(L[v[node][i].first] > L[node] + v[node][i].second){
                    L[v[node][i].first] = L[node] + v[node][i].second;

                   if(!viz[v[node][i].first]){
                   viz[v[node][i].first]=1;
                   T.pb(v[node][i].first);
                   push_heap(T.begin(),T.end(),cmp);

        }
        }

   }

}

}
int check_negative(int n){


    for( int i=1;i<=n;i++)
       for(int j=0;j<v[i].size();i++)
            if(L[v[i][j].first] > L[i] + v[i][j].second)
                   return 1;
    return 0;

}
int main()
{
    int n,m,c;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        in>>x>>y>>c;
        v[x].pb({y,c});
    }
    for(int i=2;i<=n;i++)
        L[i]=INFINITY;

    viz[1]=1;
    BF();

    if(check_negative(n))
        out<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            out<<L[i]<<" ";

    return 0;
}