#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
 
#define nmax 50001
#define inf LONG_MAX 
 
unsigned short int n, viz[nmax];
unsigned long int m;
long int d[nmax];
 
vector < pair<unsigned short int, short int> > v[nmax];
queue <unsigned short int> Q;
 
void citire()
{
    unsigned short int x, y, c;
     
    freopen("bellmanford.in", "r", stdin);
    scanf("%hu %lu", &n, &m);
    for(unsigned long int i=1; i<=m; i++)
    {
        scanf("%hu %hu %hd", &x, &y, &c);
        v[x].push_back( make_pair(y, c) );
    }
}
 
void afisare()
{
    for(unsigned short int i=2; i<=n; i++)
        printf("%ld ", d[i]);
}
 
void init()
{
    for(unsigned short int i=1; i<=n; i++)
        d[i] = inf;
    d[1] = 0;
}
 
bool bell()
{
    unsigned short int nod, i, dest;
    long int cost;
    Q.push(1);
    while( !Q.empty() )
    {
        nod = Q.front(); Q.pop();
        for(i=0; i<v[nod].size(); i++)
        {
            cost = d[nod] + v[nod][i].second; 
            dest = v[nod][i].first;
            if( cost < d[ dest ] )
            {
                d[ dest ] = cost;
                Q.push( dest );
                viz[ dest] ++;
                if( viz[dest] > n )
                    return true;
            }
        }
    }
    return false;
}
 
int main()
{
    freopen("bellmanford.out", "w", stdout);
    citire();
    init();
     
    if( bell() )
        printf("Ciclu negativ!\n");
    else
        afisare();
 
    return 0;
}