#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

struct cost_muchii
{
    int a, b, cost;
}muchii[250000];

vector <int> cost_vechi(50000);
vector <int> cost_nou(50000);

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int main()
{
    int n, m, i, j;
    fin>>n>>m;
    for(i=0; i<m; i++)
        fin>>muchii[i].a>>muchii[i].b>>muchii[i].cost;
    int sursa, nod;
    sursa = 1;
    for(i=1; i<=n; i++)
        cost_vechi[i] = 50000000;
    cost_vechi[sursa] = 0;
    cost_nou[sursa] = 0;
    cost_nou = cost_vechi;

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
            if(cost_vechi[ muchii[j].a ] + muchii[j].cost < cost_nou[ muchii[j].b ])
                cost_nou[ muchii[j].b ] = cost_vechi[ muchii[j].a ] + muchii[j].cost;
        cost_vechi = cost_nou;
    }



    for(j=0; j<m; j++)
        if(cost_vechi[ muchii[j].a ] + muchii[j].cost < cost_nou[ muchii[j].b ])
            cost_nou[ muchii[j].b ] = cost_vechi[ muchii[j].a ] + muchii[j].cost;




    if(cost_vechi == cost_nou)
    {
        //cout<<"Nu are cicluri negative"<<endl;
        for(i=2; i<=n; i++)
            fout<<cost_nou[i]<<" ";
    }
    else
        fout<<"Ciclu negativ!";


}