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

using namespace std;


int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
         
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> graph;
    vector<bool> visited;
    vector<int> counts, distances;

    for(int i = 0; i < N; ++i){
        visited.push_back(false);
        counts.push_back(0);
        graph.push_back({});
        distances.push_back(INT32_MAX);
    }

    for(int x, y, z; M > 0; --M){

        cin >> x >> y >> z;
        graph[--x].push_back(make_pair(--y, z));
    }

    queue<int> Q;
    Q.push(0);
    visited[0] = true;
    distances[0] = 0;
    counts[0]++;

    while(!Q.empty()){

        int currentNode = Q.front();
        visited[currentNode] = false;
        Q.pop();
        for(int i = 0; i < graph[currentNode].size(); ++i)
            if(distances[graph[currentNode][i].first] > distances[currentNode] + graph[currentNode][i].second){
                distances[graph[currentNode][i].first] = distances[currentNode] + graph[currentNode][i].second;
                if(!visited[graph[currentNode][i].first]){
                    visited[graph[currentNode][i].first] = true;
                    Q.push(graph[currentNode][i].first);
                    if(++counts[graph[currentNode][i].first] > N){
                        cout<< "Ciclu negativ!";
                        return 0;
                    }
                }
            }
    }
    for(int i = 1; i < N; ++i)
        cout << distances[i] << " ";

    cin.close();
    cout.close();

    return 0;
}