#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;
}