#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#include <stdio.h>
#include <stdlib.h>

#define cost first
#define nod second
#define nMax 50003
#define INF 0x3f3f3f3f

using namespace std;

vector < pair<int, int> > G[nMax];
queue < int > Q;

bitset <nMax> viz;
int nr[nMax];
int d[nMax];
int n,m;

void citire()
{
    int a,b,c;
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        cin>>a>>b>>c;
        G[a].push_back(make_pair(c, b));
    }
}

void afisare()
{
    for(int i = 2; i<=n; ++i)
    {
        if(d[i] == INF)
            cout<<0<<" ";
        else
            cout<<d[i]<<" ";
    }
}

void sol()
{
    ///initializare
    d[1] = 0;
    for(int i=2;i<=n;++i)
        d[i] = INF;
    ///initializare

    Q.push(1);
    nr[1]++;
    viz[1] = 1;

    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        viz[x] = 0;
        for(vector < pair <int,int> >::iterator it = G[x].begin(); it!=G[x].end(); ++it)
        {
            if(d[it->nod] > d[x] + it->cost)
            {
                if(viz[it->nod] == 0)
                {
                    viz[it->nod] = 1;
                    nr[it->nod]++;
                    if(nr[it->nod] > n)
                    {
                        cout<<"Ciclu negativ!";
                        exit(0);
                    }
                    Q.push(it->nod);
                }
                d[it->nod] = d[x] + it->cost;
            }
        }
    }

}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    citire();
    sol();
    afisare();

    return 0;
}