#include <iostream>

#include <cstring>

#include <cstdio>

#define MAX 100

#define INF 0x3f3f3f

using namespace std;

//有向图

struct Edge

{

    int u,v,cost;

}e[MAX];

int dist[MAX];  //最短路径

int prev[MAX];  //路径

int m,n;    //边数和顶点数

bool Bellman_Ford(int v0)

{

    int u=v0;

    for(int i=;i<=n;i++)

        dist[i]=INF;

    dist[u]=;

    for(int i=;i<=n;i++)

        for(int j=;j<m;j++)

            if(dist[e[j].v]>dist[e[j].u]+e[j].cost)

            {

                dist[e[j].v]=dist[e[j].u]+e[j].cost;

                prev[e[j].v]=e[j].u;

            }

    for(int i=;i<m;i++)

        if(dist[e[i].v]>dist[e[i].u]+e[i].cost)

            return ;

    return ;

}

int main()

{

    cin>>n>>m;

    for(int i=;i<m;i++)

        cin>>e[i].u>>e[i].v>>e[i].cost;

    if(Bellman_Ford())

        for(int i = ; i <= n; ++i) //每个点最短路

        {

            printf("%d\n", dist[i]);

        }

    else

        printf("have negative circle\n");

    return ;

}