#include <bits/stdc++.h>
using namespace std;

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

int n, m, ok;

int main(){
    ios::sync_with_stdio(false); // Faster I/O
    fin.tie(nullptr);
    fin>>n>>m;

    vector <int> dist(n+1,1e9), counter(n+1);
    vector <vector <pair <int,int>>> g(n+1);
    bitset <50001> inqueue;
    priority_queue <pair <int,int>> pq;

    int x, y, w;
    for(int i=0;i<m;i++){
        fin>>x>>y>>w;
        g[x].push_back({y,w});
    }

    dist[1]=0;
    pq.push({0,1});

    while(!pq.empty()){
        int nod=pq.top().second;
        int d=-pq.top().first;
        pq.pop();
        inqueue[nod]=0;

        for(auto next:g[nod]){
            if(dist[next.first]>dist[nod]+next.second){
                dist[next.first]=dist[nod]+next.second;
                if(!inqueue[next.first]){
                    pq.push({-dist[next.first],next.first});
                    inqueue[next.first]=1;

                    counter[next.first]++;
                    if(counter[next.first]>n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i=2;i<=n;i++)
        fout<<dist[i]<<' ';

    return 0;
}