#include <bits/stdc++.h>
#define oo 2000000000
using namespace std;


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

int hasloop;
vector< pair<pair<int, int>, int> > E;
int tata[50002];
int lung_dr[50002];
int d[50002], n, m;
queue<int> q;


void BellmanFord()
{
    int u, v, c;
    for (int i = 2; i <= n; i++)
        d[i] = oo;
    d[1] = 0;
    for (int k=1;k<n;k++)
        for (auto e : E){
            u = e.first.first;
            v = e.first.second;
            c = e.second;
            if (d[v] > d[u] + c)
            {
                lung_dr[v] = lung_dr[u] + 1;
                d[v] = d[u] + c;
                tata[v] = u;
            }
        }
    for (auto e : E){
        u = e.first.first;
        v = e.first.second;
        c = e.second;
        if (d[v] > d[u] + c)
        {
            hasloop=1;
            break;
        }
    }
    if (hasloop)
        fout<<"Ciclu negativ!\n";
    else
        for (int i = 2; i <= n; i++)
            fout << d[i] << " ";
}

int main()
{
    int i, j, p, c;
    fin >> n >> m;
    for (p = 1; p <= m; p++)
    {
        fin >> i >> j >> c;
        E.push_back({{i, j}, c});
    }
    BellmanFord();
    return 0;
}