#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]=(1<<30)-1;
    while(!coada.empty())
    {
        int curent;
        curent=coada.front();
        for(int i=0;i<(int)a[curent].size();++i)
        {
            if(dist[a[curent][i].first]>dist[curent]+a[curent][i].second)
            {
                dist[a[curent][i].first]=dist[curent]+a[curent][i].second;
                if(!inqueue[a[curent][i].first])
                {
                inqueue[a[curent][i].first]=true;
                coada.push(a[curent][i].first);
                if(++aparitii[a[curent][i].first]>(noduri-1))
                    {// trebe sa vad duapia
                        fprintf(out,"Ciclu negativ!");
                        fclose(in);
                        fclose(out);
                        return 0;
                    }
                }
            }

        }
        inqueue[curent]=false;
        coada.pop();
    }

        for(int i=2;i<=noduri;++i)
            fprintf(out,"%d ",dist[i]);


fclose(in);
fclose(out);
}