#include <fstream>
#include <queue>
#include <vector>
#define DIM 50001
#define INF 1000000
using namespace std;

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

queue <int> q;
vector < pair<int,int> > L[DIM];
int d[DIM],w[DIM],v[DIM];
int n,m,i,x,y,cost,nod,vecin;
int main (){

    fin>>n>>m;
    for (i=1;i<=n;i++){
        fin>>x>>y>>cost;
        L[x].push_back (make_pair(y,cost));
        //L[y].push_back (make_pair(x,cost));
    }
    for (i=1;i<=n;i++)
        d[i] = INF;
    q.push(1);
    v[1] = 1;
    d[1] = 0;
    while (!q.empty()){
        nod = q.front();
        q.pop();
        v[nod] = 1;
        for (int i=0;i<L[nod].size();i++){
            int vecin = L[nod][i].first;
            if (L[nod][i].second + d[nod] < d[vecin]  ){
                d[vecin] = d[nod] + L[nod][i].second;
                w[vecin]++;
                if (w[vecin] > n){
                    // avem ciclu
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                if (v[vecin] == 0){
                    q.push (vecin);
                    v[vecin] = 1;
                }

            }
        }

    }

    for (i=2;i<=n;i++)
        fout<<d[i]<<" ";

    return 0;
}