#include<bits/stdc++.h>
#define N 50100
#define P pair<int,int>
#define F first
#define S second
using namespace std;
ifstream F("bellmanford.in");
ofstream G("bellmanford.out");
int n,m,c[N],b[N],i,x,y,d;
queue<int> q;
vector<P> v[N];
int main()
{
    F>>n>>m;
    while(m--)
        F>>x>>y>>d,v[x].push_back({y,d});
    for(i=2;i<=n;++i)
        c[i]=1<<30;
    for(q.push(1);!q.empty();) {
        x=q.front(),q.pop(),++b[x];
        if(b[x]>=n)
            return G<<"Ciclu negativ!",0;
        for(auto y:v[x])
            if(c[y.F]>c[x]+y.S)
                c[y.F]=c[x]+y.S,q.push(y.F);
    }
    for(i=2;i<=n;++i)
        G<<c[i]<<' ';
    return 0;
}