/**
    -----------------------------------------------------------------------
    Bellman-Ford: ellenorzi, ha egy iranyitott grafban van negativ kor,
    ha nincs, akkor kiszamitja az 1. csomopontbol mindegyikbe a koltseget

    !!!!!!! EZ A HATEKONY ALGORITMUS A KOLTSEGEK MEGHATAROZASARA !!!!!!
    -----------------------------------------------------------------------
    futasi ido: O(V*E) / O(n*m)

    -----------------------------------------------------------------------
**/
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

ofstream fout("bellmanford.out");

void beolvas(int &n, vector<vector<pair<int, long long>>> &adj) {
    ifstream fin("bellmanford.in");
    int m;
    fin >> n >> m;
    adj.resize(n+1);
    while(m--) {
        int u, v;
        long long w;
        fin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
    }
    fin.close();
}

bool bellman_ford(int source, int n, vector<vector<pair<int, long long>>> &adj) {
    vector<long long> d(n+1, LLONG_MAX);
    vector<bool> sorban(n+1);
    vector<int> javitva(n+1);
    queue<int> q;
    d[source]=0;
    q.push(source);
    sorban[source]=true;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        sorban[u]=false;
        for(auto [v, dist] : adj[u]) {
            long long uj_tav=d[u]+dist;
            if(uj_tav<d[v]) {
                d[v]=uj_tav;
                if(sorban[v]==false) {
                    q.push(v);
                    sorban[v]=true;
                    javitva[v]++;
                    if(javitva[v]>=n) {
                        return false;
                    }
                }
            }
        }
    }
    for(int i=2; i<=n; i++) {
        fout << d[i] << ' ';
    }
    return true;
}

int main() {
    int n;
    vector<vector<pair<int, long long>>> adj;
    beolvas(n, adj);
    if(!bellman_ford(1, n, adj)) {
        fout << "Ciclu negativ!";
    }
    return 0;
}