#include <bits/stdc++.h>
#define DIMN 50010
#define INF 2000000000000000000LL
using namespace std;
vector <pair <int, int> > v[DIMN];
deque <int> dq;
int apar[DIMN] , inst[DIMN];
long long cost[DIMN];
int main()
{
    FILE *fin = fopen ("bellmanford.in","r");
    FILE *fout = fopen ("bellmanford.out","w");
    int n , m , x , y , z , c , nod , vecin , i;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&z);
        v[x].push_back(make_pair(y , z));
    }
    dq.push_back(1);
    for (i=1;i<=n;i++)
        cost[i] = INF; /// long long
    cost[1] = 0;
    inst[1] = 1;
    apar[1] = 1;
    while (!dq.empty()){

        nod = dq.front();
        dq.pop_front();

        if(apar[nod] > 100000){
            fprintf (fout,"Ciclu negativ!");
            return 0;
        }

        for (i = 0 ; i < v[nod].size() ; i++){
            vecin = v[nod][i].first;
            c = v[nod][i].second;
            if (cost[vecin] > cost[nod] + c){
                cost[vecin] = cost[nod] + c;
                apar[vecin]++;
                if(apar[vecin] > 100000){
                    fprintf (fout,"Ciclu negativ!");
                    return 0;
                }
                if (!inst[vecin]){
                    inst[vecin] = 1;
                    dq.push_back(vecin);
                }
            }
        }



        inst[nod] = 0;
    }

    for (i = 2 ; i <= n ; i++)
        fprintf (fout,"%lld ", cost[i]);

    return 0;
}