#include <fstream>
#define inf 1000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

short c[10001][10001], d[10001];
int n,p,m;

void citire(){
f>>n>>m;
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;
}
}
int belman(){
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];
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];
}
void afis(){
for(int i=1;i<=n;i++)
{
    if(d[i]==inf) d[i]=-1;
    g<<d[i]<<" ";
}
}
int main()
{
   citire(); int k=belman(); if(k==0) g<<"Ciclu negativ!"; else afis();
    return 0;
}