#include <bits/stdc++.h>
#define inf 1000000000
#define dim 50005
using namespace std;
string numeproblema="bellmanford";
ifstream fin(numeproblema+".in");
ofstream fout(numeproblema+".out");
int d[dim],n,i,x,y,z,nr[dim],m;
vector <pair<int,int> > L[dim];
deque <int> q;
bitset <dim> fr;
void bf(int nod){
int cost;
fr[nod]=1; /// se face oricum 0
d[1]=0;
q.push_back(nod);
while(!q.empty()){
    nod=q.front();
    nr[nod]++;
    if(nr[nod]>n){
    fout<<"Ciclu negativ!";
    return;
}
    q.pop_front();
    fr[nod]=0;
    for(int i=0;i<L[nod].size();i++){
        if(d[nod]+L[nod][i].second<d[L[nod][i].first]){
            d[L[nod][i].first]=d[nod]+L[nod][i].second;
            if(fr[L[nod][i].first]==0){ ///daca e in coada
               fr[L[nod][i].first]=1;
               q.push_back(L[nod][i].first);
            }
        }
    }
}
for(int i=2;i<=n;i++)
    fout<<d[i]<<" ";

}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>z;
        L[x].push_back({y,z});
    }
    for(i=1;i<=n;i++)
        d[i]=inf;
    bf(1);

}