#include <fstream>
#include <cstring>
#include <vector>
#include <list>
#include <queue>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int nmax = 50005;
const int INF = 0x3f3f3f3f;

int d[nmax];
int count[nmax];

vector<pair<int, int> >G[nmax];

//void dijkstra(bool &o, int n){
//list<int>coada;
//coada.push_back(1);
//count[1]++;
//while(!coada.empty()){
//    list<int>::iterator itr = coada.begin();
//    int x = *itr;
//    for(vector<pair<int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++it){
//        int to = it->first;
//        int cost = it->second;
//        if(d[to] > d[x] + cost){
//            coada.push_back(to);
//            count[to]++;
//            if(count[to] >= n){
//                o = true;
//                return;
//            }
//            d[to] = d[x] + cost;
//        }
//    }
//    coada.erase(itr);
//}
//}

void dijkstra(bool &o, int n){
queue<int>coada;
coada.push(1);
count[1]++;
while(!coada.empty()){
    //list<int>::iterator itr = coada.begin();
    int x = coada.front();
    coada.pop();
    for(vector<pair<int, int> >::iterator it = G[x].begin(); it != G[x].end(); ++it){
        int to = it->first;
        int cost = it->second;
        if(d[to] > d[x] + cost){
            coada.push(to);
            count[to]++;
            if(count[to] >= n){
                o = true;
                return;
            }
            d[to] = d[x] + cost;
        }
    }
   // coada.erase(itr);
}
}

int main(){

int n,m;

f>>n>>m;

for(int i=1;i<=m;++i){
    int x,y,cost;
    f>>x>>y>>cost;
    G[x].push_back(make_pair(y,cost));
}

memset(d, INF, sizeof d);

d[1] = 0;

bool o = false;

dijkstra(o,n);

if(!o){
for(int i=2;i<=n;++i)
    d[i] != INF ? g<<d[i]<<" " : g<<0<<" ";
g<<'\n';
}
else g<<"Ciclu negativ!"<<'\n';

return 0;
}