#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();
        viz[node]=0;
        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 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)
            {

                T.pb(v[node][i].first);
                push_heap(T.begin(),T.end(),cmp);
                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;

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

    return 0;
}