#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define MAX 50003

using namespace std;

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

vector<pair<int, int>> vec[MAX];
int dist[MAX];
int am[MAX];

int main() {

    int n,m,a,b,c;
    in >> n >> m;

    for(int i = 1; i <= m; i++) {
        in >> a >> b >> c;
        vec[a].push_back(make_pair(b, c));
    }

    for(int i = 1; i <= n; i++)
        dist[i] = INT_MAX/2-1;
    dist[1] = 0;

    queue<int> que;
    que.push(1);
    int nod;
    vector<pair<int, int>>::iterator it;

    while(!que.empty()) {

        nod = que.front();
        am[nod]++;
        que.pop();

        if(am[nod] > n) {
            out << "Ciclu negativ!" << '\n';
            return 0;
        }

        for(it = vec[nod].begin(); it != vec[nod].end(); it++) {

            if(dist[nod] + it->second < dist[it->first]) {

                dist[it->first] = dist[nod]+it->second;
                que.push(it->first);

            }

        }

    }

    for(int i = 2; i <= n; i++)
        out << dist[i] << " ";

    return 0;
}