#include <bits/stdc++.h>

#define pii pair<int,int>

#define DIM 50000
#define INF INT_MAX

using namespace std;

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

int n,m;
int x,y,c;

bool u[DIM+5];
int k[DIM+5];
int d[DIM+5];

vector <pii> L[DIM+5];

deque <int> q;

bool bf(int start){

    q.push_back(start);
    u[start] = 1;
    k[start] = 1;

    while(!q.empty()){
        int nod = q.front();
        q.pop_front();

        u[nod] = 0;

        for(int i = 0;i<L[nod].size();i++){
            int vec = L[nod][i].first;
            int c = L[nod][i].second;

            if(d[vec] > d[nod]+c){
                d[vec] = d[nod]+c;
                if(!u[vec]){
                    u[vec] = 1;
                    k[vec]++;

                    if(k[vec] > n){
                        g<<"Ciclu negativ!";
                        return 0;
                    }


                    q.push_back(vec);
                }
            }
        }
    }

    return 1;

}

int main(){
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>c;

        L[x].push_back({y,c});
    }

    d[1] = 0;
    for(int i=2;i<=n;i++){
        d[i] = INF;
    }


    if(bf(1)){

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

    }
    return 0;
}