#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

const int MAXN = 5e4 + 5;
const int MAXNUMAR = 1e3 + 5;
const int INF = 2e9;

using namespace std;

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

vector<pair<int,int> >graf[MAXN];
queue<int>coada;
int n,m,fr[MAXN],dp[MAXN];

void bellmanford(int start){
    for(int i = 1; i <= n; i++)
        dp[i] = INF;
    coada.push(start);
    dp[start] = 0;

    while(!coada.empty()){
        int nod = coada.front();
        coada.pop();
        fr[nod]++;
        if(fr[nod] > n){
            out<<"Ciclu negativ!"<<"\n";
            return;
        }
        for(int vecin = 0; vecin < graf[nod].size(); vecin++){
            int curent = graf[nod][vecin].first,cost = graf[nod][vecin].second;
            if(dp[nod] + cost < dp[curent]){
                dp[curent] = dp[nod] + cost;
                coada.push(curent);
            }
        }
    }
    for(int i = 2; i <= n; i++){
        if(dp[i] == INF)
            out<<0<<" ";
        else
            out<<dp[i]<<" ";
    }
}

int main()
{

    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,cost;
        in>>x>>y>>cost;
        graf[x].push_back({y,cost});
    }
    bellmanford(1);
    return 0;
}