#include <fstream>
#include <queue>

#define Nmax 50100
#define oo (1 << 30)
#define neighbour Graph[node][i].first
#define cost Graph[node][i].second

using namespace std;

vector < pair<int, int> > Graph[Nmax];
queue <int> Queue;
int N, Answer, countQueue[Nmax], Distance[Nmax];
bool inQueue[Nmax];

void BellmanFord() {

    int i, node;

    Queue.push(1);
    inQueue[1] = true;
    for(i = 2; i <= N; i++)
        Distance[i] = oo;

    while(!Queue.empty()) {

        node = Queue.front();
        Queue.pop();
        inQueue[node] = false;

        for(i = 0; i < Graph[node].size(); i++)
            if(Distance[node] + cost < Distance[neighbour]) {

                Distance[neighbour] = Distance[node] + cost;

                if(!inQueue[neighbour]) {

                    Queue.push(neighbour);
                    inQueue[neighbour] = true;
                    countQueue[neighbour]++;

                    if(countQueue[neighbour] == N) {
                        Answer = 1;
                        return;
                    }
                }
            }

    }
}
void Read() {

    int x, y, c, M;
    ifstream in("bellmanford.in");

    in >> N >> M;
    while(M--) {
        in >> x >> y >> c;
        Graph[x].push_back(make_pair(y, c));
}

    in.close();
}
void Write() {

    ofstream out("bellmanford.out");

    if(Answer == 1)
        out << "Ciclu negativ!";
    else
        for(int i = 2; i <= N; i++)
                out << Distance[i] << ' ';

    out << '\n';
    out.close();
}
int main() {

    Read();
    BellmanFord();
    Write();

    return 0;
}