#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

#define infinit 0x3f3f3f
#define nmax 50001
#define mmax 250001



using namespace std;

struct arc
{
    int src, dest, cost;
};


int n, m;
int d[nmax]; /**distante minime*/
vector<pair<int, int> > graf[nmax]; /** first - cost; second - catre nodul x*/
vector<arc> arce;


arc make_arc(int s, int dd, int c)
{
    arc aux;
    aux.src = s;
    aux.dest = dd;
    aux.cost = c;
    return aux;
}


void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        scanf("%d %d %d\n", &x, &y, &cost);
//        cin >> x >> y >> cost;
        graf[x].push_back(make_pair(cost, y));
        arce.push_back(make_arc(x, y, cost));
    }
}


bool bellman_ford()             /** true - se poate stabili drum minim; false - exista ciclu de cost negativ*/
{
    for(int i = 2; i <= n; i++)
        d[i] = infinit;
    d[1] = 0;

    for(int i = 2; i <= n; ++i)
    {
        for(vector<arc>::iterator j = arce.begin(); j != arce.end(); ++j)
        {
            int s = j->src;
            int dd = j->dest;
            int c = j->cost;
            if(d[s] + c < d[dd])
                d[dd] = d[s] + c;
        }
    }

    for(vector<arc>::iterator j = arce.begin(); j != arce.end(); ++j)
    {
        int s = j->src;
        int dd = j->dest;
        int c = j->cost;
        if(d[s] + c < d[dd])
            return false;
    }
    return true;
}


void afisare()
{
    for(int i = 2; i <= n; i++)
        cout << d[i] << ' ';
}
int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    citire();
    if(bellman_ford())
        afisare();
    else
        cout << "Ciclu negativ!";

    return 0;
}