#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) {

    priority_queue<int, vector<int>, less<int> > pq;
    vector<int> cntHeap(NMAX + 1, 0);
    bitset<NMAX + 1> inHeap;

    dist[start] = 0;
    pq.push(start);
    inHeap[start] = true;

    /*
    Tinem o lista(heap) 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(pq.empty() == false) {

       int node = pq.top();
       pq.pop();

       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(cntHeap[x.first] == n)
                    return false;

                if(inHeap[x.first] == false) {
                    pq.push(x.first);
                    inHeap[x.first] = true;
                    cntHeap[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;
}