//3. Bellman-Ford
#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<pair<int,int>> adj[50001];
int dist[50001];
int cnt[50001];
int in_queue[50001];

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

    fin>>n>>m;

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

    for (int i=1;i<=n;i++) {
        dist[i]=INT_MAX;
        in_queue[i]=0;
        cnt[i]=0;
    }

    queue<int> Q;

    dist[1]=0;
    Q.push(1);
    in_queue[1]=1;
    cnt[1]=1;

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

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

                if (in_queue[nod]==0) {
                    Q.push(nod);
                    in_queue[nod]=1;
                    cnt[nod]+=1;

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

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



}