#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define pii pair<int, int>
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int NMAX = 5 * 1e5 + 5;
const int inf = 1e9;
vector<pii> g[NMAX];
int dist[NMAX], visited[NMAX], drum[NMAX];

void blf(int source, int n) {
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }
    dist[source] = 0;
    visited[source] = 1;
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
        int curr_node = q.front();
        q.pop();
        visited[curr_node] = 0;
        for (auto neigh: g[curr_node]) {
            if (dist[neigh.first] > dist[curr_node] + neigh.second) {
                dist[neigh.first] = dist[curr_node] + neigh.second;
                drum[neigh.first] = drum[curr_node] + 1;
                if (drum[neigh.first] >= n) {
                    dist[0] = -1;
                    fout << "Ciclu negativ!";
                    return;
                }
                if (visited[neigh.first] == 0) {
                    q.push(neigh.first);
                    visited[neigh.first] = 1;
                }

            }
        }
    }
     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 x,y,z;
        fin >> x >> y >> z;
        g[x].push_back({y,z});

    }
    blf(1,n);


}