#include <bits/stdc++.h>
#define NMAX 50001
#define MMAX 250001
#define INF 1e9

using namespace std;

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

int n, m, nr, vf[MMAX*2], urm[MMAX*2], last[NMAX], cost[MMAX];
int dist[NMAX], used[MMAX];
bool foundC;
queue < int > Q;

void adauga(int nod, int v, int pret)
{
    vf[++nr] = v;
    urm[nr] = last[nod];
    last[nod] = nr;

    cost[nr] = pret;
}

void citire()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a, b, c; fin>>a>>b>>c;
        adauga(a, b, c);
    }
}

void bellman(int x)
{
    for(int i=1; i<=n; i++)
        dist[i] = INF;
    dist[x] = 0;

    Q.push(x);

    while(!Q.empty() && !foundC)
    {
        int nod = Q.front();
        Q.pop();

        for(int k = last[nod]; k; k = urm[k])
        {
            if(dist[ vf[k] ] > dist[nod] + cost[k])
            {
                dist[ vf[k] ] = dist[nod] + cost[k];
                used[k] ++;

                Q.push(vf[k]);

                if(used[k]>n)
                    foundC = true;
            }
        }
    }

    if(foundC)
        fout<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; i++)
            fout<<dist[i]<<' ';


}


int main()
{
    citire();
    bellman(1);

    return 0;
}