#include <fstream>
#include <vector>
#include <queue>
#define inf 100000000
using namespace std;

struct nod{

    int nodv,val;

}temp;

int n,m,c,xs,ys,ok=1;
vector < vector < nod > > Graf;
queue < int > q;
vector < int > cost;
vector < int > vizitat;
vector < int > father;

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


 void citesc(){

    f >> n >> m ;
    Graf.resize(n+1);
    cost.resize(n+1,inf);
    vizitat.resize(n+1);
    father.resize(n+1);
    for(int i=1;i<=m;i++){

        f >> xs >> ys >> c;
        temp.nodv = ys , temp.val = c;
        Graf[xs].push_back(temp);

}
    f.close();
 }

int bellman_ford(int start){


    int top;
    ++father[start];
    q.push(start);
    cost[start] = 0;
    vizitat[start] = 1;
        while(!q.empty()){

            top = q.front();
            q.pop();
            vizitat[top] = 0;

                for(vector<nod>::iterator it = Graf[top].begin();it!=Graf[top].end();++it){
                    if(cost[it->nodv] > cost[top] + it->val){
                        cost[it->nodv] = cost[top] + it->val;
                       if(!vizitat[it->nodv]){
                        q.push(it->nodv);
                        vizitat[it->nodv] = 1;
                    }
                    ++father[it->nodv];
                    if(father[it->nodv] >= n)
                     return 0;
                 }
               }
             }
           return 1;
           }

void afisez(){


 if(!ok)
    g << "Ciclu negativ" << '\n';
    else
    for(int i=2;i<=n;i++)
        g << cost[i] << " ";
}

int main(){

    citesc();
    bellman_ford(1);
    afisez();

 g.close();
 return 0;
}