#include<cstdio>
#include<vector>
#include<cstdlib>
#include<limits.h>
using namespace std;

struct Edge{
    int from,to,weight;
}edges[100000];

int dist[10000],n,m;

void init(){
    scanf("%d %d",&n,&m);

    for(int i=0;i<m;i++){
        scanf("%d %d %d",&edges[i].from,&edges[i].to,&edges[i].weight);
    }
}

void bellmanFord(int start){
    bool somethingHasChanged;

    /// initialize all distances to be inf. and the distance to the start is 0
    fill(dist,dist+n,INT_MAX);
    dist[start]=0;

    for(int i=0;i<n-1;i++){///n-1 iterations
        somethingHasChanged = false;///we mark that initially nothing has changed

        for(int j=0;j<m;j++){///for each edge
            if(dist[edges[j].from]==INT_MAX)continue;///if the distance to the beginning is inf then no point in trying to update distance to the end

            if(dist[edges[j].to] > dist[edges[j].from] + edges[j].weight){///if the distance can be updated with a better one
                dist[edges[j].to] = dist[edges[j].from] + edges[j].weight;///we do it
                somethingHasChanged=true;///and mark if something has changed
            }
        }

        if(!somethingHasChanged)break;///if nothing has changed this iteration then it wont change the next one since we will do the exact same thing
    }

    ///we must do one more iterration.
    somethingHasChanged = false;
    for(int j=0;j<m;j++){
        if(dist[edges[j].from]==INT_MAX)continue;

        if(dist[edges[j].to] > dist[edges[j].from] + edges[j].weight){
            dist[edges[j].to] = dist[edges[j].from] + edges[j].weight;
            somethingHasChanged=true;
        }
    }

    if(somethingHasChanged){/// If something changes in this one then there is a cycle with a negative weight
        printf("There is a cycle with negative weight\n");
        exit(0);
    }

    ///the algorithm ends here. dist[i] is the minimal distance from the start node to node i. Note that if there are components that are unreachable from the start node
    ///the dist to those nodes will be INT_MAX
}

void print(){
    for(int i=0;i<n;i++){
        printf("dist to %d is %d\n",i,dist[i]);
    }
}

int main(){
    init();
    bellmanFord(0);
    print();
}
/**
5 5
0 1 3
0 2 2
4 1 1
2 4 -1
1 3 1
*/