#include <bits/stdc++.h>
#define NMAX 50000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int n,m;
struct elem {
    int poz,val,generation;
};
vector< pair<int,int> >adj[NMAX+5];
queue< elem > q;
int dist[NMAX+5];

void bellmanford(int start) {
    for (int i=1; i<=n; i++) dist[i]=INT_MAX;
    dist[start]=0;
    q.push({start,0,1});

    while (!q.empty()) {
        auto X=q.front();
        q.pop();

        if (X.generation==n+1) {
            fout<<"Ciclu negativ!\n";
            exit(0);
        }

        for (auto i : adj[X.poz]) {
            if (X.val+i.second<dist[i.first]) {
                dist[i.first]=X.val+i.second;
                q.push({i.first,dist[i.first],X.generation+1});
            }
        }
    }

    for (int i=1; i<=n; i++) {
        if (i==start) continue;
        fout<<dist[i]<<' ';
    }
}
int main()
{
    fin>>n>>m;
    int x,y,c;
    for (int i=0; i<m; i++) {
        fin>>x>>y>>c;
        adj[x].push_back({y,c});
    }

    bellmanford(1);
    return 0;
}