#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct edge
{
int u,v,wt;
};
int main()
{
int n;
cin>>n;
int e;
cin>>e;
edge edges[e+1];
for(int i=0;i<e;i++)
{
cin>>edges[i].u>>edges[i].v>>edges[i].wt;
}
int d[n+1];
for(int i=0;i<=n;i++)
d[i]=INT_MAX;
d[1]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<e;j++)
{
if(d[edges[j].v]>d[edges[j].u]+edges[j].wt)
{
if(i==n-1)
{
cout<<"Negative cycle found"<<endl;
break;
}
d[edges[j].v]=d[edges[j].u]+edges[j].wt;
}
}
}
for(int i=1;i<=n;i++)
cout<<d[i]<<" ";
cout<<endl;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBlbmRsICdcbicKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBlZGdlCnsKICBpbnQgdSx2LHd0OyAgCn07CgppbnQgbWFpbigpCnsKICAgIGludCBuOwogICAgY2luPj5uOwogICAgCiAgICBpbnQgZTsKICAgIGNpbj4+ZTsKICAgIAogICAgZWRnZSBlZGdlc1tlKzFdOwogICAgZm9yKGludCBpPTA7aTxlO2krKykKICAgIHsKICAgICAgICBjaW4+PmVkZ2VzW2ldLnU+PmVkZ2VzW2ldLnY+PmVkZ2VzW2ldLnd0OwogICAgfQogICAgCiAgICBpbnQgZFtuKzFdOwogICAgZm9yKGludCBpPTA7aTw9bjtpKyspCiAgICBkW2ldPUlOVF9NQVg7CiAgICAKICAgIGRbMV09MDsKICAgIAogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBmb3IoaW50IGo9MDtqPGU7aisrKQogICAgICAgIHsKICAgICAgICAgICAgaWYoZFtlZGdlc1tqXS52XT5kW2VkZ2VzW2pdLnVdK2VkZ2VzW2pdLnd0KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihpPT1uLTEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY291dDw8Ik5lZ2F0aXZlIGN5Y2xlIGZvdW5kIjw8ZW5kbDsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGRbZWRnZXNbal0udl09ZFtlZGdlc1tqXS51XStlZGdlc1tqXS53dDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIAogICAgZm9yKGludCBpPTE7aTw9bjtpKyspCiAgICBjb3V0PDxkW2ldPDwiICI7CiAgICAKICAgIGNvdXQ8PGVuZGw7CiAgICByZXR1cm4gMDsKfQ==