#include <fstream>
#include <bitset>
#include <queue>
#include <vector>
using namespace std;
ofstream fout("bellmanford.out");
ifstream fin("bellmanford.in");
const int NMAX = 50010;
const int INF = 1 << 30;

struct Nod
{
    int dest, cost;
};

int n, m, ok;
int Drum[NMAX], Nr[NMAX];
vector<Nod> Graf[NMAX];
bitset<NMAX> inQueue;
queue<int> Q;

void bellmanford(int first)
{
    for(int i=1; i<=n; i++)
        Drum[i] = INF;
    inQueue.reset();

    Drum[first] = 0;
    Q.push(first);
    inQueue[first] = true;

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        inQueue[nod] = false;

        for(auto x : Graf[nod]) {
            if(Drum[x.dest] > Drum[nod] + x.cost) {
                Drum[x.dest] = Drum[nod] + x.cost;
                if(!inQueue[x.dest]) {
                    inQueue[x.dest] = true, Q.push(x.dest);
                    if(++Nr[x.dest] > n) {
                        ok = 1;
                        return;
                    }
                }
            }
        }
    }

    return;
}

int main()
{
    fin >> n >> m;
    for(int i=1, x, y, c; i<=m; i++) {
        fin >> x >> y >> c;
        Graf[x].push_back({y,c});
    }

    bellmanford(1);

    if(ok) fout << "Ciclu negativ!\n";
    else for(int i=2; i<=n; i++) fout << Drum[i] << ' ';
    return 0;
}