#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;

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

vector <pair <int,int> >v[NMAX];
vector <int> Q;
int check[NMAX],d[NMAX],aparitii[NMAX];
int n,m,ok=1;

void bellman(int x)
{
    int p,u,j;
    Q.push_back(x); d[x]=0; check[x]=1; aparitii[x]=1; p=u=0;
    while(p<=u)
    {
        j=Q[p++]; check[j]=0;
        for(auto i:v[j])
        {
            if(d[j]+i.second<d[i.first])
            {
                d[i.first]=d[j]+i.second;
                if(check[i.first]==0)
                {
                    Q.push_back(i.first); u++;
                    check[i.first]=1;
                }
                aparitii[i.first]++;
            }
        }
        if(aparitii[j]>=n) {fout<<"Ciclu negativ!"<<"\n";ok=0; return ;}
    }
}

int main()
{
    int i,x,y,z;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(i=1;i<=n;i++)
    {
        d[i]=INT_MAX;
    }
    bellman(1);
    if(ok)
    {
        for(i=2;i<=n;i++)
        {
            fout<<d[i]<<" ";
        }
    }
    return 0;
}