#include <stdio.h>
#include <vector>
#include <string.h>
#include <bitset>
#include <queue>
#define nmax 50000
#define inf 0x3f3f3f3f
using namespace std;
FILE *fin=fopen("bellmanford.in","r");
FILE *fout=fopen("bellmanford.out","w");
int n,m,poz,neg[nmax+5],dist[nmax+5];
vector< pair < int,int > > graf[nmax+5];
queue<int> que;
bitset<nmax+5> viz;
int main()
{
    int x,y,z;
    fscanf(fin,"%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d %d %d",&x,&y,&z);
        graf[x].push_back({y,z});
    }
    memset(dist,inf,sizeof(dist));
    dist[1]=0;
    viz[1]=1;
    que.push(1);
    while(!que.empty())
    {
        x=que.front();
        if(++neg[x]==n)
        {
            fprintf(fout,"Ciclu negativ!\n");
            return 0;
        }
        viz[x]=0;
        que.pop();
        for(auto vec:graf[x])
            {
                y=vec.first;
                z=vec.second;
                if(dist[y]>dist[x]+z)
                {
                    dist[y]=dist[x]+z;
                    if(!viz[y])
                    {
                        que.push(y);
                        viz[y]=1;
                    }
                }
            }
    }
    for(int i=2;i<=n;i++)
        fprintf(fout,"%d ",dist[i]);
    return 0;
}