#include <fstream>
#include <vector>
#define INF 99999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair < int,int > >G[50001];
int st[500000],b[50005],d[50005],ok,vf,q[50005],n,m,i,x,y,cost,u;
int main()
{
 f>>n>>m;
 for(i=1;i<=m;i++){
    f>>x>>y>>cost;
    G[x].push_back(make_pair(y,cost));
 }
 for(i=2;i<=n;i++)
    d[i]=INF;
 st[1]=1;
 u=1;
 vf=1;
 while(vf<=u){
    b[st[vf]]++;
    if(b[st[vf]]>=n){
        ok=1;
        break;
    }
    for(i=0;i<G[st[vf]].size();i++)
        if(d[G[st[vf]][i].first]>d[st[vf]]+G[st[vf]][i].second){
                d[G[st[vf]][i].first]=d[st[vf]]+G[st[vf]][i].second;
                st[++u]=G[st[vf]][i].first;
        }
    vf++;
 }
 if(ok==1)
    g<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            g<<d[i]<<" ";
    return 0;
}