#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
#define nmax 50002
#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];
pair<unsigned short int, short int> x;
queue <unsigned short int> Q;

void cit()
{
    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 afis()
{
    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, vecin;
    long int cost;
    Q.push(1);
    while( !Q.empty() )
    {
        nod = Q.front();
        Q.pop();
        for(i=0;i<v[nod].size();i++)
        {
            x=v[nod][i];
            cost = d[nod] + x.second;
            vecin = x.first;
            if( cost < d[ vecin ] )
            {
                d[vecin] = cost;
                Q.push( vecin );
                viz[vecin]++;
                if( viz[vecin] > n )
                    return true;
            }
        }
    }
    return false;
}

int main()
{
    freopen("bellmanford.out", "w", stdout);
    cit();
    init();

    if( bell() )
        printf("Ciclu negativ!\n");
    else
        afis();

    return 0;
}