#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#define node pair<int,int>
using namespace std;

const char nl = '\n';
const int inf = 1e9 + 2;
const int NMAX = 5 * 1e4 + 5;
vector<node> graph[NMAX];
int dist[NMAX], visited[NMAX];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
void bellmanford (int source, int n) {
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }
    dist[source] = 0;
    visited[source] = 1;
    queue<node> q;

    q.push({source, dist[source]});
    while (!q.empty()) {
        int curr_node = q.front().first;
        q.pop();
        if (visited[curr_node] == n - 1) {
            dist[0] = -1;
            return;
        }
        for (auto neigh: graph[curr_node]) {
            if (dist[neigh.first] > dist[curr_node] + neigh.second) {
                dist[neigh.first] = dist[curr_node] + neigh.second;
                q.push({neigh.first, dist[neigh.second]});
                visited[neigh.first]++;
            }
        }
    }





    // for (int i = 1; i < n; i++) {
    //     pq.push({source, dist[source]});
    //     while (!pq.empty()) {
    //         int cur_node = pq.top().first;
    //         pq.pop();
    //         for (auto neigh: graph[cur_node]) {
    //             if (dist[neigh.second] > dist[cur_node] + neigh.first) {
    //                 dist[neigh.second] = dist[cur_node] + neigh.first;
    //                 pq.push({neigh.second, -dist[neigh.second]});
    //             }
    //         }
    //     }

    // }
    // pq.push({source, dist[source]});
    //     while (!pq.empty()) {
    //         int cur_node = pq.top().first;
    //         pq.pop();
    //         for (auto neigh: graph[cur_node]) {
    //             if (dist[neigh.second] > dist[cur_node] + neigh.first) {
    //                 dist[0] = -1;
    //             }
    //         }
    //     }

    




    // for (int i = 1; i <= n - 1;i++) {
    //     for (int j = 1; j <= n; j++) {
    //         for (auto neigh: graph[j]) {
    //             if (neigh.second + dist[j] < dist[neigh.first]) {
    //                 dist[neigh.first] = neigh.second + dist[j];
    //             }
    //         }
    //     }
    // }
    // for (int j = 1; j <= n; j++) {
    //     for (auto neigh: graph[j]) {
    //             if (neigh.second + dist[j] < dist[neigh.first]) {
    //                dist[0] = -1;
    //             }
    //         }
    // }
   
}
int main () {
    int n,m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x,y,z;
        fin >> x >> y >> z;
        graph[x].push_back({y,z});
       
    }
    bellmanford(1,n);
    if (dist[0] == -1) {
        fout << "Ciclu negativ!";
    }
    else 
    {
        for (int i = 2; i <= n; i++) {
        fout << dist[i] << " ";
        }
    }
   
}