/// Aceasta sursa este pentru problema
/// https://infoarena.ro/problema/bellmanford
/// Punctaj: 100
/// Grupa Medie (pt seniori)

#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#include <queue>

#define DIM 50000
#define INF 1000000005

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

//ifstream f("in.in");
//ofstream g("out.out");

int n,m,x,y,cost,nod,vec,lung;
vector <pair<int,int>> l[DIM+5];
deque <int> q;
int viz[DIM+5];
int cnt[DIM+5];
int D[DIM+5];

int main(){

    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>cost;
        l[x].push_back({y,cost});
    }
    D[1] = 0;
    for(int i=2;i<=n;i++){
        D[i] = INF;
    }

    q.push_back(1);
    viz[1] = 1;
    cnt[1]++;
    while(!q.empty()){
        nod = q.front();
        viz[nod] = 0;
        for(int i=0;i<l[nod].size();i++){
            vec = l[nod][i].first;
            lung = l[nod][i].second;
            if(D[vec] > D[nod] + lung){
                D[vec] = D[nod] + lung;
                if(viz[vec] == 0){
                    cnt[vec]++;
                    if(cnt[vec]>n){
                        g<<"Ciclu negativ!";
                        f.close();
                        g.close();
                        return 0;
                    }

                    viz[vec] = 1;
                    q.push_back(vec);
                }
            }
        }
        q.pop_front();
    }

    for(int i=2;i<=n;i++){
        g<<D[i]<<" ";
    }


    f.close();
    g.close();
    return 0;
}