#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==

Ngo2CjEgMiA1CjEgNCA5CjMgMSAxCjIgNiAxNQo1IDMgMjAKNSA0IDEw

6
6
1 2 5
1 4 9
3 1 1
2 6 15
5 3 20
5 4 10