#include <iostream>
#include <fstream>
#define Mmax 250000
#define Nmax 50002
#include <vector>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct muchie
{
    int x,y,cost;
};
int n,m;
muchie v[Mmax];

void Citire ()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
}

void Bellman_Ford ()
{
    vector <int> cost_nou(Nmax,0);
    vector <int> cost_vechi(Nmax,0);
    int i,j;
    const int inf=200000000;
    for (i=1;i<=n;i++)
        cost_nou[i]=cost_vechi[i]=inf;

    cost_nou[1]=cost_vechi[1]=0;

    for (i=1;i<=n+1;i++)
    {
        for (j=1;j<=m;j++)
            if (cost_vechi[v[j].x]+v[j].cost<cost_nou[v[j].y])
                cost_nou[v[j].y]=cost_vechi[v[j].x]+v[j].cost;

        if (cost_nou==cost_vechi) break;
        else
        cost_vechi=cost_nou;
    }
    if (i==n+1) fout<<"Ciclu negativ!";
    else
    for (i=2;i<=n;i++)
        fout<<cost_vechi[i]<<" ";
}
int main()
{
   Citire();
   Bellman_Ford();
    return 0;
}