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

using namespace std;
const int INF = 2000000000;
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]=INF;
        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 [vecin,pondere]:adj[nod]) {
            if (dist[nod]+pondere<dist[vecin]) {
                dist[vecin]=dist[nod]+pondere;

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

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

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



}