#include<fstream>
#include <vector>
#include <queue>
#define NMAX 50010
#define INF 1000000000

using namespace std;

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

int n;
int cmin[NMAX], nrpus[NMAX];

vector<int>a[NMAX];
vector<int>cost[NMAX];
queue<int>coada;

void citire();
void bell();

int main()
{
    citire();
    bell();
    fout<<'\n';
    fout.close();
    return 0;
}

void citire()
{
    int m, x, y, costv, i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>costv;
        cost[x].push_back(costv);
        a[x].push_back(y);
    }
}

void initializare()
{
    int i;
    for(i=1;i<=n;i++)
        cmin[i]=INF;
    cmin[1]=0;
}

void bell()
{
    int inc, sf, i, x, y;
    inc=sf=1; coada.push(1);
    while(!coada.empty())
    {
        x=coada.front();
        for(y=0; y<a[x].size(); y++)
            if(cmin[x]+cost[x][y]<cmin[a[x][y]])
            {
                cmin[a[x][y]]=cmin[x]+cost[x][y];
                coada.push(a[x][y]);
                nrpus[a[x][y]]++;
                if(nrpus[a[x][y]]>=n)
                {
                    fout<<"Ciclu negativ!";
                    return;
                }
            }
    }
    for(i=2;i<=n;i++)
        fout<<cmin[i]<<' ';
}