#include <iostream>
#include <fstream>
#include <vector>

#define DIM 50001
#define inf 300000

class Node{
public:
    int p;
    int dist;
};

class adj_node{
public:
    int y,cost;
    adj_node(int y, int cost): y{y},cost{cost}{}
};

std::vector<adj_node> G[DIM];
Node node[DIM];
int n,m;
std::ifstream f("bellmanford.in");
std::ofstream g("bellmanford.out");

void read(){
    f>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++){
        f>>x>>y>>c;
        G[x].push_back(adj_node(y,c));
    }
    f.close();
}

void init(int s){
    for(int i=1;i<=n;i++){
        node[i].p=-1;
        node[i].dist=inf;
    }
    node[s].dist=0;
}



void relax(int x, int y, int cost){
    if(node[y].dist>node[x].dist+cost)
        node[y].dist=node[x].dist+cost;
}

bool bellman(int s){
    init(s);
    for(int i=0;i<n-1;i++){
        for(int j=1;j<=n;j++){
            for(auto q:G[j]){
                relax(j,q.y,q.cost);
            }
        }
    }
    for(int j=1;j<=n;j++){
        for(auto q:G[j]){
            if(node[q.y].dist>node[j].dist+q.cost)
                return false;
        }
    }
    return true;
}

void print(){
    if(!bellman(1))
        g<<"Ciclu negativ!";
    else{
        for(int i=2;i<=n;i++)
            g<<node[i].dist<<" ";
    }
    g.close();
}
int main() {
    read();
    print();
    return 0;
}