#include <bits/stdc++.h>
#define Nmax 50001
#define INF 2e9+1
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
queue <int> q;
struct Graph
{
    vector <pair<int,int> >v;
};
Graph G[Nmax];
int d[Nmax];
int cnt[Nmax];
bitset <Nmax> viz;
int main()
{int n,m,i,j,k,c,x;
f>>n>>m;
for(k=1;k<=m;k++)
{
    f>>i>>j>>c;
    G[i].v.push_back({j,c});
}
bool ok=true;
fill(d+1,d+n+1,INF);
d[1]=0;
q.push(1);
viz[1]=true;
while(ok and !q.empty())
{
    x=q.front();
    q.pop();
    viz[x]=false;
    if(d[x]<INF)
    for(i=0;i<G[x].v.size();i++)
        if(d[G[x].v[i].first]>d[x]+G[x].v[i].second)
        {
            d[G[x].v[i].first]=d[x]+G[x].v[i].second;
            if(!viz[G[x].v[i].first])
            {
                if(cnt[G[x].v[i].first]>n)
                ok=false;
                else
                {
                    viz[G[x].v[i].first]=true;
                    q.push(G[x].v[i].first);
                    cnt[G[x].v[i].first]++;
                }
            }
        }
}
if(!ok) g<<"Ciclu negativ!";
else
{
    for(i=2;i<=n;i++)
    if(d[i]==INF) g<<0<<' ';
    else g<<d[i]<<' ';
}

    return 0;
}