#include <fstream>
#include <vector>
#include <deque>
#define NMAX 50020
#define INF 200000000
#define pb push_back
using namespace std;

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

struct muchie{
    int nodul,costul;
};
muchie mm(int a,int b) {
    muchie c;
    c.nodul=a;c.costul=b;
    return c;
}
int n,i,m,a,b,c;
vector <muchie> A[NMAX];
deque <int> D;
int cm[NMAX];
bool cneg=false;

void push(int nod,int cost) {
    if (cm[nod]<cost) {return;}
    cm[nod]=cost;
    D.pb(nod);
}
void afis() {
    if (cneg) {g << "Ciclu negativ!" << '\n';return;}
    for (i=2;i<=n;i++) g << cm[i] << ' ';
    return;
}
int main () {
    f >> n >> m;
    for (i=1;i<=m;i++) {
        f >> a >> b >> c;
        A[a].pb(mm(b,c));
    }
    for (i=1;i<=n;cm[i]=INF,i++);
    cm[1]=0;
    D.pb(1);
    while (!D.empty() && !cneg) {
        int nod=D.front();D.pop_front();
        for (int j=0;j<A[nod].size() && !cneg;j++)
            push(A[nod][j].nodul,cm[nod]+A[nod][j].costul);
    }
    afis();
    f.close();g.close();
    return 0;
}