#include <bits/stdc++.h>
#define ll unsigned long long

using namespace std;
int n,m;
vector<pair<int,int>>G[100001];
int d[100001],incoada[100001],viz[100001];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int main(){
    fin>>n>>m;
    while(m--){
        int x,y,cost;
        fin>>x>>y>>cost;
        G[x].push_back({y,cost});
    }
    for(int i = 2;i<=n;i++){
        d[i]= 1000000000;
    }
    queue<int>Q;
    Q.push(1);
    incoada[1]=1;
    while(!Q.empty()){
        int nod = Q.front();
        Q.pop();
        incoada[nod]=0;
        viz[nod]++;
        if(viz[nod]>1){
            fout<<"Ciclu negativ!";
            return 0;
        }

        for(auto x : G[nod]){
            int vecin = x.first;
            int cost = x.second;
            if(d[vecin]>d[nod]+cost){
                d[vecin] = d[nod]+cost;
                if(incoada[vecin] == 0){
                    Q.push(vecin);
                    incoada[vecin] = 1;
            }
            }
        }
    }
    for(int i = 2; i<=n; i++)
        fout<<d[i]<<" ";
    return 0;
}