#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>
#include<math.h>
using namespace std;
FILE*in=fopen("bellmanford.in","r");
FILE*out=fopen("bellmanford.out","w");
int noduri,muchii,dist[50001],aparitii[50001];
queue<int> coada;
bool inqueue[50001];
bool print_text=false;
vector <pair<int,int> > a[50001];
int main()
{
    fscanf(in,"%d%d",&noduri,&muchii);
    for(int i=0;i<muchii;++i)
    {
        int nod,nodz,cost;
        fscanf(in,"%d%d%d",&nod,&nodz,&cost);
        a[nod].push_back(make_pair(nodz,cost));
    }
    coada.push(1);
    inqueue[1]=true;
    for(int i=2;i<=noduri;++i)
        dist[i]=1001;
    while(!coada.empty())
    {
        int curent;
        curent=coada.front();
        for(int i=0;i<(int)a[curent].size();++i)
        {
            if(!inqueue[a[curent][i].first] && dist[a[curent][i].first]>dist[curent]+a[curent][i].second)
            {
                inqueue[a[curent][i].first]=true;
                coada.push(a[curent][i].first);
                if(++aparitii[a[curent][i].first]>(noduri-1))
                    {
                        while(!coada.empty())
                            coada.pop();
                        print_text=true;
                        break;
                    }
            }
            dist[a[curent][i].first]=min(dist[a[curent][i].first],dist[curent]+a[curent][i].second);
        }
        inqueue[curent]=false;
        coada.pop();
    }
    if(print_text)
        fprintf(out,"Ciclu negativ!");
    else
        for(int i=2;i<=noduri;++i)
            fprintf(out,"%d ",dist[i]);


fclose(in);
fclose(out);
}