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

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

bitset<NMAX> inque;
int apque[NMAX];
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;
    if (inque[nod]) return;
    if (apque[nod]>n) {cneg=true;return;}
    D.pb(nod);inque[nod]=1;apque[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,apque[i]=0,i++);
    cm[1]=0;
    D.pb(1);inque[1]=1;apque[1]=1;
    while (!D.empty() && !cneg) {
        int nod=D.front();D.pop_front();inque[nod]=0;
        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;
}