#include <fstream>
#include <vector>
#include <queue>
#include <list>
#define INF -1
using namespace std;
struct e{int n,c;};

int main(){
    ifstream ifs("bellmanford.in");
    ofstream ofs("bellmanford.out");
    int N,M;
    ifs>>N>>M;

    vector<list<e> > v(N);

    for(int i=0;i<M;i++){
        int a;e t;ifs>>a>>t.n>>t.c;a--;t.n--;
        v[a].push_back(t);
    }

    vector<bool> in(N,0);in[0]=true;
    vector<int> nr(N,0);nr[0]=1;
    vector<int> ans(N,-1); ans[0]=0;

    queue<int> q;q.push(0);
    bool s=true;
    while(!q.empty()&&s){
        int f=q.front();
        q.pop();
        in[f]=false;

        for(list<e>::iterator i=v[f].begin();i!=v[f].end();i++){
            int c=ans[f]+i->c;
            if((ans[i->n]==-1)||(c<ans[i->n])){
                ans[i->n]=c;
                if(!in[i->n]){
                    if(nr[i->n]>N){
                        ofs<<"Ciclu negativ!\n";
                        s=false;
                        break;
                    }else{
                        q.push(i->n);
                        nr[i->n]++;
                        in[i->n]=true;
                    }
                }
            }
        }
    }

    if(s)
        for(int i=1;i<N;i++)
            ofs<<ans[i]<<" ";

}