#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

#define NMAX 50010

const int oo = 100000000;

int N,M,BF[NMAX],InQNumber[NMAX];
bool InQueue[NMAX],isCycle;
vector<pair<int, int>> G[NMAX];
queue<int> Q;

void Init(){
    for (int i = 2; i <= N; ++i) {
        BF[i] = oo;
    }
    
    BF[1] = 0;
    Q.push(1);
    InQueue[1] = true;
    InQNumber[1] = 1;
}

void Read(){
    f>>N>>M;int x,y,c;
    for (int i = 1; i <= M; ++i) {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y, c));
    }
}

void Solve(){
    while (!Q.empty()) {
        int Node = Q.front(); Q.pop();
        InQueue[Node] = false;
        
        for (vector<pair<int, int>>::iterator it=G[Node].begin(); it != G[Node].end() ; ++it) {
            int Neighbour = (*it).first;
            int NeighboursCost = (*it).second;
            
            if (BF[Neighbour] > BF[Node] + NeighboursCost) {
                BF[Neighbour] = BF[Node] + NeighboursCost;
                
                if (!InQueue[Neighbour]) {
                    Q.push(Neighbour);
                    InQueue[Neighbour] = true;
                    InQNumber[Neighbour]++;
                    
                    if (InQNumber[Neighbour] > N) {
                        isCycle = true;
                        return;
                    }
                    
                }
            }
        }
        
    }
}

void Write(){
    if (isCycle) {
        g<< "Ciclu negativ!";
    }else{
        for (int i = 2; i <= N; ++i) {
            g<<BF[i]<<" ";
        }
    }
}

int main()
{
    Read();
     Init();
    Solve();
    Write();
    return 0;
}