#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

const int INF = 2000000000; 
const int N_MAX = 50005;

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

struct Edge {
    int u, v, cost;
};

int dist[N_MAX];
vector<Edge> edges; 


void BellmanFord(int N)
{
    for (int i = 1; i <= N - 1; ++i) {
        bool changed = false; 

        for (const auto& edge : edges) {
            if (dist[edge.u] != INF && dist[edge.u] + edge.cost < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.cost;
                changed = true;
            }
        }
        
        if (!changed) break; 
    }

    bool hasNegativeCycle = false;
    for (const auto& edge : edges) {
        if (dist[edge.u] != INF && dist[edge.u] + edge.cost < dist[edge.v]) {
            hasNegativeCycle = true;
            fout << "negativ";
            return;
        }
    }

    for (int i = 2; i <= N; ++i) {
        fout << dist[i] << " ";
    }
}

int main() {

    int N, M;
    fin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v, c;
        fin >> u >> v >> c;
        edges.push_back({u, v, c});
    }

    for (int i = 1; i <= N; ++i) {
        dist[i] = INF;
    }
    dist[1] = 0; 
    
    BellmanFord(N);

    fin.close();
    fout.close();

    return 0;
}