#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#define message "Ciclu negativ!"

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
int updates[50005], distances[50005];
vector<pair<int, int>> adjancy[50005];
bool didIputitinQ[50005];
queue<int> Q;

void step(){
    distances[0] = 0;
    Q.push(0);
    didIputitinQ[0] = true;
    while(!Q.empty()){
        int nod = Q.front();
        Q.pop();
        didIputitinQ[nod] = false;
        for (auto & i : adjancy[nod]) {
            if(updates[i.first] == n){
                g<<message;
                exit(0);
            }
            if(!didIputitinQ[i.first] && distances[nod] + i.second < distances[i.first]){
                didIputitinQ[i.first] = true;
                Q.push(i.first);
                distances[i.first] = distances[nod] + i.second;
                updates[i.first]++;
            }
        }
    }
}

int main() {
    f>>n>>m;
    for (int i = 0; i < m; ++i) {
        int source, destination, cost;
        f>>source>>destination>>cost;
        adjancy[source - 1].emplace_back(destination - 1, cost);
    }
    memset(distances, 11, sizeof(distances));
    step();
    for (int i = 1; i < n; ++i) {
        g<<distances[i]<<' ';
    }
    return 0;
}