#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,c,dist[50005],viz[50005];
bool inqueue[50005];
const int inf = 100000000;
vector<pair<int,int>> v[50005];
int main() {
        fin>>n>>m;
        for (int i = 1;i<=m;++i) {
                fin>>x>>y>>c;
                v[x].emplace_back(y,c);
        }
        dist[1] = 0;
        for (int i = 2;i<=n;++i)
                dist[i] = inf;
        queue<int> q;
        q.push(1);
        inqueue[1] = 1;
        bool ok = 1;
        while(!q.empty()) {
                int crtn = q.front();
                q.pop();
                viz[crtn]++;
                if (viz[crtn]>=n) {
                        ok = 0;
                        break;
                }
                inqueue[crtn] = 0;
                for (auto &[nod,cost] : v[crtn]) {
                        if (dist[crtn]+cost<dist[nod]) {
                                dist[nod] = min(dist[crtn]+cost,dist[nod]);
                                if (inqueue[nod]==0) {
                                        q.push(nod);
                                        inqueue[nod] = 1;
                                }
                        }
                }
        }
        if (!ok) {
                fout<<"Ciclu negativ!";
        } else {
                for (int i = 2;i<=n;++i)
                        fout<<dist[i]<<" ";
        }
        return 0;
}