#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")

using namespace std;

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

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

struct muchie{
    int a;
    int b;
    int c;
} edge[maxM];
inline bool cmp(const muchie &a, const muchie &b){
    return a.c < b.c;
}

int dp[maxN];
int n, m;

void _set(){
    for(int i=1; i<=n; i++)
        dp[i] = INF;
}

int main (){
    ios_base::sync_with_stdio(false); fin.tie(0); fout.tie(0);

    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>edge[i].a>>edge[i].b>>edge[i].c;
    sort(edge+1, edge+m+1, cmp);

    _set();
    dp[1] = 0;

    int steps=0, nod, nxt, cst;
    bool modif;
    do{
        modif = false;
        steps++;

        for(int i=1; i<=m; i++){
            nod = edge[i].a;
            nxt = edge[i].b;
            cst = edge[i].c;

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

                dp[nxt] = dp[nod] + cst;
                modif = true;
            }
        }

        if(steps > n){
            fout<<"Ciclu negativ!";
            return 0;
        }
    }while(modif != false);

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