#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50010

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector< pair < int, int > > edges[NMAX];
queue<int> nodes;
int distances[NMAX], inQueue[NMAX], nrOfUpdates[NMAX];

int main()
{
    int n, m, x, y, cost;
    fin >> n >> m;
    for (int i=1; i<=m; i++) {
        fin >> x >> y >> cost;
        edges[x].push_back(make_pair(y, cost));
    }
    for (int i=1; i<=n; i++)
        distances[i] = (1<<30);
    nodes.push(1);
    nrOfUpdates[1] = 1;
    inQueue[1] = 1;
    distances[1] = 0;
    while(!nodes.empty()) {
        int currentNode = nodes.front();
        nodes.pop();
        inQueue[currentNode] = 0;
        vector<pair <int, int > >::iterator it;
        for (it=edges[currentNode].begin(); it!=edges[currentNode].end(); ++it) {
            if (distances[currentNode] + (*it).second < distances[(*it).first]) {
                distances[(*it).first] = distances[currentNode] + (*it).second;
                if (inQueue[(*it).first] == 0) {
                    nodes.push((*it).first);
                    inQueue[(*it).first] = 1;
                    nrOfUpdates[(*it).first]++;
                    if (nrOfUpdates[(*it).first] == n + 1) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for (int i=2; i<=n; i++)
        fout << distances[i] << " ";
    return 0;
}