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

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;
int p=0, u=0;
coada.push_back(1);
count[1]++;
while(p<=u){
    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;
            ++u;
        }
    }
    coada.erase(itr);
    ++p;
}
}

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;
}