#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int INF = 2e9;
const int MAX_N = 50005;

int n, m, x, y, c;

struct edge{
    int nxt;
    int cst;
}; vector <edge> e[MAX_N];

priority_queue <pair<int, int>> best;
int crt, nxt, cst, dist[MAX_N], viz[MAX_N];
void bellman_ford(int start){
    for(int i=1; i<=n; i++)
        dist[i] = INF;
    dist[start] = 0;

    best.push({dist[start], start});
    while(!best.empty()){
        crt = best.top().second;
        best.pop();

        for(auto muchie : e[crt]){
            nxt = muchie.nxt;
            cst = muchie.cst;

            if(dist[nxt] > dist[crt] + cst){
                dist[nxt] = dist[crt] + cst;
                viz[nxt]++;

                if(viz[nxt] > n){
                    fout<<"Ciclu negativ!";
                    return;
                }

                best.push({-dist[nxt], nxt});
            }
        }
    }

    /// nu exista ciclu negativ
    for(int i=2; i<=n; i++)
        fout<<dist[i]<<" ";
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>m;
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        e[x].push_back({y, c});
    }

    bellman_ford(1);
    return 0;
}