#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];

priority_queue <pii, vector<pii>,greater<pii>> q;

bool bf(int start){

    q.push({0,start});
    u[start] = 1;
    k[start] = 1;

    while(!q.empty()){
        pii top = q.top();
        q.pop();

        int nod = top.second;

        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(!u[vec] && d[vec] > d[nod]+c){
                d[vec] = d[nod]+c;
                u[vec] = 1;
                k[vec]++;

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


                q.push({c,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;
}