#include <fstream>
#include <vector>
#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, Count[Nmax], Distance[Nmax];
bool inQueue[Nmax], Solution;

void BellmanFord(int Start) {

    int i, Node;

    Queue.push(Start);
    Distance[Start] = 0;

    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[Neighbour] > Distance[Node] + Cost) {

                Distance[Neighbour] = Distance[Node] + Cost;

                if(!inQueue[Neighbour]) {
                    Queue.push(Neighbour);
                    inQueue[Neighbour] = true;
                    Count[Neighbour]++;

                    if(Count[Neighbour] == N) {
                        Solution = false;
                        return;
                        }

                    }

                }

        }

    Solution = true;

}
void Read() {

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

    in >> N >> M;

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

    in.close();

}
void Write() {

    ofstream out("bellmanford.out");

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

    out << '\n';
    out.close();

}
int main() {

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

    return 0;

}