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

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



using namespace std;




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

queue<int> coada;
int viz[nmax];
int nrviz[nmax]; /**numar de vizitari; daca nrviz[i] este n, atunci avem ciclu de cost negativ*/

void citire()
{
    int m;
    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);
        graf[x].push_back(make_pair(y, cost));
    }
}


bool bellman_ford()             /** true - se poate stabili drum minim; false - exista ciclu de cost negativ*/
{
    coada.push(1);
    viz[1] = true;
    nrviz[1] = 1;

    while(!coada.empty())
    {
        int x = coada.front();
        viz[x] = false;
        coada.pop();
        for(vector<pair<int, int> >::iterator it = graf[x].begin(); it != graf[x].end(); ++it)
            if(d[x] + it->second < d[it->first])
            {
                d[it->first] = d[x] + it->second;
                if(!viz[it->first])
                {
                    nrviz[it->first]++;
                    if(nrviz[it->first] == n)
                        return false;
                    coada.push(it->first);
                    viz[it->first] = true;
                }
            }
    }
    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();
    for(int i = 2; i <= n; i++)
        d[i] = infinit;

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

    return 0;
}