/*
 * Simple BellmanFord in O(N*M)
 * Algoritmul ia fiecare muchie de N ori.
 * Drumul minim va trece prin maxim N noduri.(altfel avem ciclu negativ)
 * De fiecare data cand luam muchiile odata ne apropiem cu on nod de acest drum minim.
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

const int NMAX = 50000;
const int MMAX = 250000;
const int INF = 0x7ffffff;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n; int m;

vector< vector < pair<int, int> > > g(NMAX + 1, vector< pair<int, int> >(0));

vector<int> dist(NMAX + 1, INF);

void read() {

	fin >> n >> m;

	for(int i = 1; i <= m ; ++i) {

		int x; int y; int cost;
		fin >> x >> y >> cost;
        g[x].push_back({y, cost});
	}
}

bool bellmanFord(int start) {

    queue<int> q;
    bitset<NMAX + 1> inQueue;
    vector<int> cntQueue(NMAX + 1, 0);

    dist[start] = 0;
    q.push(start);

    /*
    Tinem o lista cu nodurile al caror cost a fost imbunattit.
    Nu are rost sa ne uitam la muhciile nodurilor al caror cost nu a fost imbunatati
    */

    while(q.empty() == false) {

       int node = q.front();
       q.pop();
       inQueue[node] = 0;

       for(pair<int, int> x : g[node]) {
            /*Folosesc doar muchiile nodurilor al caror cost a fost imbunatatit. */

            if(dist[node] + x.second < dist[x.first]) {

                 dist[x.first] = dist[node] + x.second;

                if(inQueue[x.first] == 0) {

                    /*  Daca intalnesc din nou nodul in coada insemna ca am trecut la un nou set de muchii, din alt ciclu */

                    if(cntQueue[x.first] == n)
                        return false;

                    q.push(x.first);
                    inQueue[x.first] = 1;
                    cntQueue[x.first]++;
                }
            }
       }
    }

    return true;
}

int main() {

	read();

	if(bellmanFord(1))
        for(int i = 2; i <= n; ++i)
            fout << dist[i] << " ";
    else
        fout << "Ciclu negativ!";

	return 0;
}