#include <iostream>
#include <vector>
#include <limits.h>

#include <fstream>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

#define N 10000

struct Edge {
    int idx1;
    int idx2;
    int weight;
};

bool visited[N];
int dist[N];

int n, m;
vector<Edge> edge_list;

void init_dist(int max_node) {
    for (int i = 1; i <= max_node; i++)
        dist[i] = INT_MAX;
}

void init_visited(int max_node) {
    for (int i = 1; i <= max_node; i++)
        visited[i] = false;
}

int BellManFord(int start_node) {

    init_dist(n);
    init_visited(n);
    
    dist[start_node] = 0;

    // relax all edges n - 1 times.
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 0; j < m; j++) {

            int src = edge_list[j].idx1;
            int dest = edge_list[j].idx2;
            int weight = edge_list[j].weight;
            if (dist[src] != INT_MAX && dist[src] + weight < dist[dest]) {
                    dist[dest] = dist[src] + weight;
                }
        }
    }

    // check for negative-weight cycles.
    for (int i = 0; i < m; i++) {

        int src = edge_list[i].idx1;
        int dest = edge_list[i].idx2;
        int weight = edge_list[i].weight;
        if (dist[src] != INT_MAX && dist[dest] > dist[src] + weight) {
            return -1;
        }
    }

    return 0;
}

int main() {

    int s, x, y, c;

    in >> n >> m;

    s = 1;

    // scanf("%d %d %d", &n, &m, &s);

    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &c);
        edge_list.push_back({x, y, c});
    }

    int err = BellManFord(s);
    if (err == -1) {
        out << "Ciclu negativ!";
        // printf("Graph has negative-weight cycles\n");
        return 0;
    }

    for (int i = 2; i <= n; i++) {
        if (dist[i] != INT_MAX)
            out << dist[i] << " ";
            // printf("%d ", dist[i]);
        else { 
            out << "NaN ";
            // printf("NaN ");
        }
    }
    printf("\n");

    return 0;
}