#include <fstream>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int inf=100000000;
short d[10001];
int n,p,m;

void afis(){
for(int i=1;i<=n;i++)
{
    if(d[i]==inf) d[i]=-1;
    g<<d[i]<<" ";
}
}
int main()
{
  f>>n>>m;
  short c[n][n];
  p=1;
int i,j,pr;
for(int i=1;i<=n;i++)
    d[i]=inf;
d[p]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
    c[i][j]=inf;
while(f>>i>>j>>pr){
    c[i][j]=pr;
}

 for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(c[j][k]!=inf && d[k]>d[j]+c[j][k])
    d[k]=d[j]+c[j][k];

int nr=0;
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(c[j][k]!=inf && d[k]>d[j]+c[j][k])
 {g<<"Ciclu negativ!"; nr++;}

  if(nr!=0) afis();

    return 0;
}