#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#define Nmax 50000
#define inf 0x3f3f3f3f
using namespace std;

void BellmanFord(int size, const vector<pair<int, int>> graf[Nmax], int source) {

    ofstream g("bellmanford.out");
    
    int d[Nmax];
    for (int i = 0; i < size; ++i) {
        d[i] = inf;
    }
    d[source] = 0;
    for(int k = 0; k < size - 1; ++k)
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < graf[i].size(); ++j) {
                int node = graf[i][j].first;
                int cost = graf[i][j].second;
                if (d[node] > d[i] + cost) {
                    d[node] = d[i] + cost;
                }
            }
        }
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < graf[i].size(); ++j) {
            int node = graf[i][j].first;
            int cost = graf[i][j].second;
            if (d[node] > d[i] + cost) {
                g << "Ciclu negativ!\n";
                return;
            }
        }
    }
    for (int i = 1; i < size; ++i) {
        g << d[i] << ' ';
    }
}


int main() {
    ifstream f("bellmanford.in");
    int n, m, v, d, s, p, source;
    string line;
    vector < pair< int, int > > graf[Nmax];

    f >> n >> m;

    for (int i = 0; i < m; ++i) {
        f >> d >> s >> p;
        graf[--d].push_back({ --s, p });
        
    }
    source = 0;
    BellmanFord(n, graf, source);
}