#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50010
#define INF 1999999
using namespace std;

int counter[NMAX], dmin[NMAX], n, m;
bool cnegativ, inqueue[NMAX];
vector < pair<int, int> > L[NMAX];

void citire();
void bellman_ford();
void afisare();

int main()
{
    citire();
    bellman_ford();
    afisare();
    return 0;
}

void citire()
{
    int i, x, y, c;
    FILE*fin=fopen ("bellmanford.in", "r");
    fscanf(fin, "%d %d", &n, &m);
    for (i=1; i<=m; ++i){
        fscanf(fin, "%d %d %d", &x, &y, &c);
        L[x].push_back(make_pair(y, c));
    }
    fclose(fin);
    return;
}

void bellman_ford()
{
    int vf, i;
    queue <int> Q;

    for (i=2; i<=n; ++i) dmin[i]=INF;
    Q.push(1); counter[1]=1;

    while (!Q.empty() && !cnegativ){
        vf=Q.front();
        Q.pop();
        inqueue[vf]=false;

        for (i=0; i<L[vf].size(); ++i)
            if (dmin[L[vf][i].first]>dmin[vf]+L[vf][i].second){
                dmin[L[vf][i].first]=dmin[vf]+L[vf][i].second;
                ++counter[L[vf][i].first];
                if (counter[L[vf][i].first]>=n)
                    cnegativ=true;
                if (!inqueue[L[vf][i].first]){
                    Q.push(L[vf][i].first);
                    inqueue[L[vf][i].first]=true;
                }
            }
    }
    return;
}

void afisare()
{
    int i;
    FILE*fout=fopen ("bellmanford.out", "w");
    if (cnegativ)
        fprintf(fout, "Ciclu negativ!");
        else
        for (i=2; i<=n; ++i)
            fprintf (fout, "%d ", dmin[i]);
    fprintf (fout, "\n");
    fclose(fout);
    return;
}