#include<fstream>
#include<vector>
using namespace std;

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

int d[50010],n,m,aux,a,b,ls,ld,c,i,j,vizitat[50010];
vector<pair<int,int> > v[50010];
int coada[1000000];
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;++i)
    d[i]=1<<30;
    ls=ld=1;
    coada[1]=1;
    vizitat[1]=1;
    while(ls<=ld)
    {
       aux=coada[ls++];
       if(vizitat[aux]==n)
       {fout<<"Ciclu negativ!";
       return 0;}
       for(unsigned int i=0;i<v[aux].size();++i)
       {
           if(d[v[aux][i].first]>d[aux]+v[aux][i].second)
           {
               d[v[aux][i].first]=d[aux]+v[aux][i].second;
               coada[++ld]=v[aux][i].first;
               vizitat[v[aux][i].first]++;
           }
       }
    }
    for(i=2;i<=n;++i)
    fout<<d[i]<<" ";
    return 0;
}