#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector < pair <int , int > > v[NMAX];
vector <int> Q;
int D[NMAX];
int prez[NMAX],chk[NMAX],n,ok=1;
void BLF(int x)
{
    int p,u,nc;
    Q.push_back(x);
    D[x]=0;
    p=u=0;
    prez[x]=1;
    chk[x]=1;
    while(p<=u)
    {
        nc=Q[p];
        p++;
        chk[nc]=0;
        for(auto i:v[nc])
        {
            if(D[nc]+i.second < D[i.first]){
            D[i.first]=D[nc]+i.second;
            if(chk[i.first]==0)Q.push_back(i.first),u++,chk[i.first]=1;
            prez[i.first]++;

        }

        }
        if(prez[nc]>=n) {fout<<"Ciclu negativ!"<<"\n";ok=0;return;}
    }
}
int main()
{
    int m,i,x,y,z;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>z;
        v[x].push_back({y,z});

    }
    for(i=1;i<=n;++i)
        D[i]=INT_MAX;
    BLF(1);
    if(ok)
    for(i=2;i<=n;++i)
    fout<<D[i]<<" ";
    return 0;
}