#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int NMAX = 5e4+2;
const int INF = 0x3f3f3f;
int n,m,dist[NMAX],vf[NMAX];
vector<pii> v[NMAX];

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

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, z;
        fin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    memset(dist, INF, sizeof(dist));
    set<pii> s;
    dist[1] = 0;
    s.insert({0, 1});
    while(!s.empty()){
        int nod = s.begin()->second;
        s.erase(s.begin());
        for(auto [vecin, cost]: v[nod]){
            if(dist[vecin] > dist[nod] + cost){
                dist[vecin] = dist[nod] + cost;
                if(++vf[vecin] > n){
                    fout << "Ciclu negativ!";
                    return 0;
                }
                s.insert({dist[vecin], vecin});
            }
        }
    }
    for(int i = 2; i <= n; i++){
        fout << dist[i] << " ";
    }
    return 0;
}