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

vector<vector<pair<int,int>>>graf(NMAX);
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>>q;
vector<int>dist(NMAX,1e9);
vector<int>cnt(NMAX);
int n,m;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int dijkstra(int node){
    dist[node]=0;
    q.push({node,0});
    while(!q.empty()){
        auto small=q.top();
        q.pop();

        if(small.second > dist[small.first])
            continue;
        for(const auto& vec : graf[small.first]){
            int nxt=vec.first;
            int cost=vec.second+small.second;

            if(cost < dist[nxt])
            {
                dist[nxt]=cost;
                q.push({nxt,dist[nxt]});
                cnt[nxt]++;
                if(cnt[nxt]>n){
                    g<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    f>>n>>m;
    int x,y,c;
    for(int i=1; i<=m; ++i){
        f>>x>>y>>c;
        graf[x].push_back({y,c});
    }
    dijkstra(1);
    for(int i=2; i<=n; ++i)
        g<<dist[i]<<' ';
    return 0;


}