#include<fstream>
#include<fstream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

queue <int> Queue;
vector < pair<int,int> > v[50010];
int n,m,dist[50010],contor[50010],A=1;
bool inQ[50010];

void citire() {

    ifstream in("bellmanford.in");
    int i,y,c,x;
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    in.close();

}

void bellmanford(int start) {

    int vecin,nod,i;
    Queue.push(start);
    dist[start]=0;
    contor[start]=1;

    while(!Queue.empty()) {
        nod=Queue.front();
        inQ[nod]=0;
        Queue.pop();
        for(i=0;i<v[nod].size();i++) {
            vecin=v[nod][i].first;
            if(dist[vecin]>dist[nod]+v[nod][i].second) {
                dist[vecin]=dist[nod]+v[nod][i].second;
                if(inQ[vecin]==0) {
                    inQ[vecin]=1;
                    contor[vecin]++;
                    Queue.push(vecin);
                }
            }

            if(contor[vecin]>n)
                A=0;
        }
    }


}

void solve() {

    int i;
    for(i=1;i<=n;i++)
        dist[i]=9999999;
    bellmanford(1);

}

void afisare() {

    ofstream out("bellmanford.out");
    int i;
    if(A==0)
        out<<"Ciclu negativ!"<<'/n';
    else
        for(i=2;i<=n;i++)
            out<<dist[i]<<' ';
    out<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}