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