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

using namespace std;

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

const int N_MAX = 50001;
int n, m;

struct path{
    int nod, cost;
};

vector<path> vecini[N_MAX];
vector<int> costs, added;

void BellmanFord(int sursa){
    queue<int> Q;

    Q.push(sursa);

    costs[sursa] = 0;

    while(not Q.empty()){
        int nod = Q.front(), x;

        for(const path& vecin : vecini[nod]){
            x = costs[nod] + vecin.cost;
            if(costs[vecin.nod] > x){
                costs[vecin.nod] = x;

                Q.push(vecin.nod);

                added[vecin.nod]++;
                if(added[vecin.nod] >= n){
                    g << "Ciclu negativ!";
                    exit(0);
                }
            }
        }

        Q.pop();
    }
}

int main()
{
    f >> n >> m;

    costs.resize(n + 1, INT_MAX);
    added.resize(n + 1, 0);

    for(int i = 0, n1, n2, c; i < m; ++i){
        f >> n1 >> n2 >> c;
        vecini[n1].push_back(path{n2, c});
    }

    BellmanFord(1);

    for(int i = 2; i <= n; ++i) /// nu se scrie pt nodul sursa (1)
        g << costs[i] << ' ';

    return 0;
}