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

using namespace std;

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

const int INF = 1 << 30;
/*
struct Edge
{
    int u;
    int v;
    int cost;
};

int bellmanFord(vector<Edge> &edges, vector<int> &dist, int N, int M)
{
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            int u = edges[j].u;
            int v = edges[j].v;
            int cost = edges[j].cost;
            if(dist[v] > dist[u] + cost){
                if(i == N-1){
                    return -1;
                }
                dist[v] = dist[u] + cost;
            }
        }
    }
    return 0;
}
*/
int bellmanFord_optimized(int N, vector<vector<pair<int, int>>> &adj, vector<int> &dist)
{
    vector<bool> in_queue(N+1, false);
    vector<int> cnt_in_queue(N+1, 0);
    queue<int> q;
    q.push(1);
    in_queue[1] = true;
    cnt_in_queue[1] = 1;
    dist[1] = 0;

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

        in_queue[currNode] = false;
        for(int i = 0; i < adj[currNode].size(); i++){
            int newNode = adj[currNode][i].first;
            int add_cost = adj[currNode][i].second;

            if(dist[newNode] > dist[currNode] + add_cost){
                dist[newNode] = dist[currNode] + add_cost;
                if(!in_queue[newNode]){
                    if(cnt_in_queue[newNode] > N){
                        return -1;
                    }
                    else{
                        q.push(newNode);
                        cnt_in_queue[newNode]++;
                        in_queue[newNode] = true;
                    }
                }
            }
        }
    }
    return 0;
}

int main()
{
    int N, M;
    input >> N >> M;
    //vector<Edge> edges(M);
    vector<vector<pair<int, int>>> adj(N+1);

    for(int i = 0; i < M; i++){
        int u, v, cost;
        input >> u >> v >> cost;
        //edges[i] = {u-1, v-1, cost};
        adj[u].push_back({v, cost});
    }

    vector<int> dist(N+1, INF);
    dist[0] = 0;

    //int sol = bellmanFord(edges, dist, N, M);
    int sol = bellmanFord_optimized(N, adj, dist);
    if(sol == -1){
        output << "Ciclu negativ!";
    }else {
        for(int i = 2; i <= N; i++){
            output << dist[i] << " ";
        }
    }
    return 0;
}