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

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int,int>> adj[50001];
int dist[50001];
int contor[50001];
int in_queue[50001];

int main() {

    int n,m;
    fin>>n>>m;

    int x,y,c;

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

    for (int i=1;i<=n;i++) {
        dist[i]= 2000000000;
        in_queue[i]=0;
        contor[i]=0;
    }
    queue<int> q;

    q.push(1);
    in_queue[1]=1;
    dist[1]=0;
    contor[1]=1;

    while (q.size()>0) {
        int nod=q.front();
        q.pop();
        in_queue[nod]=0;


        for (auto [vecin,pondere]:adj[nod]) {
            if (dist[vecin]>dist[nod]+pondere) {
                dist[vecin]=dist[nod]+pondere;

                if (in_queue[vecin]==0) {
                    q.push(vecin);
                    in_queue[vecin]=1;
                    contor[vecin]+=1;

                    if (contor[vecin] > n) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }

            }
        }
    }

    for (int i=2;i<=n;i++) {
        if (dist[i]==2000000000) fout<<0<<' ';
        else
            fout<<dist[i]<<' ';

    }



}