#include <bits/stdc++.h>
#define _nod pair<int,int>

using namespace std;

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

const int INF  = 1e9;
const int maxN = 50005;
const int maxM = 250005;

int n, a, b, c;
vector <_nod> v[maxN];

bool ciclu = false;
priority_queue <_nod> q;
int viz[maxN], dp[maxN];
void belman_ford(int start){

    for(int i=1; i<=n; i++)
        dp[i] = INF;
    dp[start] = 0;

    int nod, nxt, cst;

    q.push({0, start});
    while(!q.empty()){
        nod  = q.top().second;
        q.pop();

        for(int i=0; i<v[nod].size(); i++){
            nxt = v[nod][i].first;
            cst = v[nod][i].second;

            if(dp[nxt] > dp[nod] + cst){
                dp[nxt] = dp[nod] + cst;
                viz[nxt]++;

                if(viz[nxt] > n){
                    ciclu=true;
                    fout<<"Ciclu negativ!";
                    return;
                }

                q.push({-dp[nxt], nxt});
            }
        }
    }
}

int main (){
    fin>>n;

    int edgeCnt; fin>>edgeCnt;
    while(edgeCnt--){
        fin>>a>>b>>c;
        v[a].push_back({b, c});
    }

    belman_ford(1);
    if(ciclu == true)
        return 0;




    for(int i=2; i<=n; i++)
        fout<<dp[i]<<" ";
    return 0;
}