#include<stdio.h>
#include<string.h>
#include<vector>
#define MAXV 50000
#define MAXE 200000
#define INF 1000000000
struct Edge
{
    int dst;
    int cost;
};
void init();
void blf(int nod);
FILE*fin,*fout;
std::vector<int> neighbors[MAXV];
Edge edges[MAXE];
bool visited[MAXE];
int shortestPath[MAXV];
int E,V;
bool ok=1;
int main()
{
    fin=fopen("bellmanford.in","r");
    fout=fopen("bellmanford.out","w");
    fscanf(fin,"%d%d",&V,&E);
    for(int i=0;i<E;i++)
    {
        int src,dst,cst;
        fscanf(fin,"%d%d%d",&src,&dst,&cst);
        src--;
        dst--;
        neighbors[src].push_back(i);
        edges[i].dst=dst;
        edges[i].cost=cst;
    }
    init();
    int i=0;
    do
    {
        memset(visited,0,sizeof(visited));
        ok=1;
        blf(0);
        i++;
    }while(i<V && !ok);
    if(ok)
    {
        for(int i=1;i<V;i++)
        {
            fprintf(fout,"%d ",shortestPath[i]);
        }
    }
    else
    {
        fprintf(fout,"Ciclu negativ!");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
void init()
{
    shortestPath[0]=0;
    for(int i=1;i<V;i++)
    {
        shortestPath[i]=INF;
    }
}
void blf(int nod)
{
    for(int i=0;i<neighbors[nod].size();i++)
    {
        if(!visited[neighbors[nod][i]])
        {
            visited[neighbors[nod][i]]=1;
            if(shortestPath[edges[neighbors[nod][i]].dst]>shortestPath[nod]+edges[neighbors[nod][i]].cost)
            {
                ok=0;
                shortestPath[edges[neighbors[nod][i]].dst]=shortestPath[nod]+edges[neighbors[nod][i]].cost;
            }
            blf(edges[neighbors[nod][i]].dst);
        }
    }
}