#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

queue < int > q;
vector < pair < int , int > > v[50100];
int n,m,i,x,y,c,nod,cost_intre,vecin,inCoada[50100],cost_bell[50100],fv[50100];

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back({y,c});
    }

    for(i=1;i<=n;i++)cost_bell[i]=INT_MAX/2;
    q.push(1);cost_bell[1]=0;inCoada[1]=1;
    while(!q.empty())
    {
        nod=q.front();
        fv[nod]++;
        if(fv[nod]>=n)
        {
            g<<"Ciclu negativ!";
            return 0;
        }
        q.pop();

        for(i=0;i<v[nod].size();i++)
        {
            vecin=v[nod][i].first;
            cost_intre=v[nod][i].second;

            if(cost_bell[vecin]>cost_bell[nod]+cost_intre)
            {
                cost_bell[vecin]=cost_bell[nod]+cost_intre;
                if(inCoada[vecin]==0)inCoada[vecin]=1,q.push(vecin);
            }
        }
    }

    for(i=2;i<=n;i++)g<<cost_bell[i]<<" ";
    return 0;
}