#include <bits/stdc++.h>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
deque<int> q;
vector<pair<int,int> > v[50010];
int i,n,m,x,y,u,viz[50010],dist[50010];
bool in[500010];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>u;
        v[x].push_back({y,u});
    }
    memset(dist,127,sizeof(dist));
    dist[1]=0;in[1]=1;
    q.push_back(1);
    while(q.size())
    {
        x=q.front();
        q.pop_front();
        viz[x]++;
        if(viz[x]==n+1)
        {
            g<<"Ciclu negativ!";
            return 0;
        }in[x]=0;
        for(auto it:v[x])
            if(dist[it.first]>dist[x]+it.second)
            {
                dist[it.first]=dist[x]+it.second;
                if(!in[it.first])
                    q.push_back(it.first),in[it.first]=1;
            }
    }
    for(i=2;i<=n;i++)
        g<<dist[i]<<' ';
    return 0;
}