#include <fstream>
#include <vector>
#include <queue>
#include <functional>

#define doila32 2000000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n,m,i,j,nod,nr,dismin[50010],x,y,c,cnt[50010];
bool incoada[50010],ok;
vector< pair <int,int> > l[50010];
//priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > qu;
queue<int> qu;

void bellman_ford()
{
    qu.push(1);
    while(!qu.empty())
    {
        nod=qu.front();
        qu.pop();
        incoada[nod]=0;
        for(int i=0;i<l[nod].size();++i)
        {
            if(dismin[nod]+l[nod][i].second<dismin[l[nod][i].first])
            {
                dismin[l[nod][i].first]=dismin[nod]+l[nod][i].second;
                if(incoada[l[nod][i].first]==0)
                {
                    if(cnt[l[nod][i].first]>n)
                    {
                        fout<<"Ciclu negativ!\n";
                        ok=1;
                        return ;
                    }
                    qu.push(l[nod][i].first);
                    incoada[l[nod][i].first]=1;
                    ++cnt[l[nod][i].first];
                }
            }
        }
    }
}

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

    for(i=2;i<=n;++i)
        dismin[i]=doila32;

    bellman_ford();

    if(ok==0)
    {
        for(i=2;i<=n;++i)
            fout<<dismin[i]<<" ";
    }
    return 0;
}