#include <bits/stdc++.h>
#define NMAX 50550

using namespace std;

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

int n, m;
struct edge {
    int destination, weight;
};

vector<edge> edges[NMAX];
int visited[NMAX];

void bellmanford(int start) {
    queue<int> q;
    vector<int> distance(n + 1, INT_MAX);
    q.push(start);
    distance[start] = 0;

    while(!q.empty()) {
        int current = q.front();
        q.pop();

        for(auto x : edges[current]) {
            if(distance[x.destination] > distance[current] + x.weight) {
                distance[x.destination] = distance[current] + x.weight;
                q.push(x.destination);
                visited[x.destination]++;
                if(visited[x.destination] >= n) {
                    fout << "Ciclu negativ!";
                    return;
                }
            }
        }
    }
    for(int i = 2; i <= n; i++)
        fout << distance[i] << ' ';
}

int main() {
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        int node1, node2, weight;
        fin >> node1 >> node2 >> weight;
        edges[node1].push_back({node2, weight});
    }
    bellmanford(1);
}