#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 100001
#define INFINITY ((1 << 14)-1)
typedef struct {
    int source;
    int dest;
    int weight;
} Edge;
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source){
    //int *distance = new int;//malloc(nodecount * sizeof *distance);
    int distance[N];
	int i, j;
    for (i=0; i < nodecount; ++i)
      distance[i] = INFINITY;
    distance[source] = 0;

    for (i=0; i < nodecount; ++i) {
        for (j=0; j < edgecount; ++j) {
            if (distance[edges[j].source] != INFINITY) {
                int new_distance = distance[edges[j].source] + edges[j].weight;
                if (new_distance < distance[edges[j].dest])
					distance[edges[j].dest] = new_distance;
            }
        }
    }
    for (i=0; i < edgecount; ++i) {
        if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
            puts("Negative edge weight cycles detected!");
            free(distance);
            return;
        }
    }
    for (i=1; i < nodecount; ++i) {
        printf("%d ",(distance[i]==INFINITY)?0:distance[i]);
    }
    free(distance);
    return;
}

int main(void){
    int n,m,i;
	Edge edges[N];
    freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=0;i<m;++i){
		scanf("%d%d%d",&edges[i].source,&edges[i].dest,&edges[i].weight);
		--edges[i].source;
		--edges[i].dest;
	}
    BellmanFord(edges, m, n, 0);
    return 0;
}