#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMax 50001
#define oo 999999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, x, y, z, d[NMax], frecv[NMax];
bool ok;
bool viz[NMax];
struct muchie{
    int nod, dist;
};
vector <muchie> v[NMax];
struct comp {
    bool operator() (int &a, int &b) {
        return d[a] > d[b];
    }
};
priority_queue <int, vector<int>, comp> pq;
void bellmanford(int R) {
    pq.push(R);
    int nod, vSize, dist, fiu;
    while(!pq.empty()) {
        nod = pq.top();
        pq.pop();
        vSize = v[nod].size();
        viz[nod] = false;
        for(int i = 0; i < vSize; ++i) {
            fiu = v[nod][i].nod;
            dist = v[nod][i].dist;
            if(dist + d[nod] < d[fiu]) {
                d[fiu] = d[nod] + dist;
                if(viz[fiu])
                    continue;
                viz[fiu] = true;
                pq.push(fiu);
                frecv[fiu]++;
                if(frecv[fiu] > n) {
                    fout<<"Ciclu negativ!";
                    ok = true;
                    return;
                }
            }

        }
    }
}
int main()
{
    fin>>n>>m;
    muchie noua;
    for(int i = 1; i <= m; ++i) {
        fin>>x>>y>>z;
        noua.nod = y;
        noua.dist = z;
        v[x].push_back(noua);
    }
    for(int i = 1; i <= n; ++i) {
        d[i] = oo;
    }
    int R = 1;
    d[R] = 0;
    bellmanford(R);
    if(!ok)
    for(int i = 2; i <= n; ++i) {
        fout<<d[i]<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}