#include<bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
vector<vector<pair<int,int>>>muchii(50001,vector<pair<int,int>>(0));
int n,m,inf=1e9,in_coada[50001],ct[50001],este_ciclu=0;
vector<int>distanta(50001,inf);
int main()
{in>>n>>m;
for(int i=1;i<=n;i++)
{int x,y,z;
in>>x>>y>>z;
muchii[x].push_back({y,z});
}
distanta[1]=0;
queue<int>q;
q.push(1);
while(!este_ciclu&&!q.empty())
{int nod=q.front();
ct[nod]++;
q.pop();
in_coada[nod]=0;
if(ct[nod]>n)
este_ciclu=1;
else
{for(auto x:muchii[nod])
    if(distanta[x.first]>distanta[nod]+x.second)
    {distanta[x.first]=distanta[nod]+x.second;
    if(!in_coada[x.first])
    {in_coada[x.first]=1;
    q.push(x.first);

    }

    }
}
}
  if(este_ciclu)
  out<<"Ciclu negativ!";
else
for(int i=2;i<=n;i++)
out<<distanta[i]<<" ";

}