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