#include <cstdio>
#include <vector>
#include <utility>
#include <climits>
#include <queue>
#define Nmax 50001

using namespace std;
FILE *f1,*f2;
int u,v,c,d[Nmax],m,n,i,use[Nmax],ok,x,ct[Nmax];
vector <pair <int,int> > a[Nmax];
queue <int> q;

int main()
{f1 = fopen("bellmanford.in","r");
f2 = fopen("bellmanford.out","w");
fscanf(f1,"%d %d",&n,&m);
for (i=1;i<=n;i++) {fscanf(f1,"%d%d%d",&u,&v,&c);a[u].push_back(make_pair(v,c));}
for (i=1;i<=n;i++) {d[i]=LONG_MAX;}
d[1]=0;q.push(1);use[1]=1;ok=0;

while (!q.empty() && !ok)
{x=q.front();q.pop();use[x]=0;

for (i=0;i<(int)a[x].size();i++)
if (d[a[x][i].first]>d[x]+a[x][i].second)
{d[a[x][i].first]=d[x]+a[x][i].second;
if (!use[a[x][i].first])
{if (ct[a[x][i].first]>m) ok=1;
else
{q.push(a[x][i].first);use[a[x][i].first]=1;
ct[a[x][i].first]++;
}
}
}
}

if (ok) fprintf(f2,"Ciclu negativ!\n");
else
for (i=2;i<=n;i++) fprintf(f2,"%d ",d[i]);

fclose(f1);
fclose(f2);

    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.