#include<stdio.h>
#include<string.h>
#include<vector>
#define MAXV 50000
#define MAXE 250000
#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 coada[MAXV];
int pr=0,ult=-1;
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;
        pr=0,ult=-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)
{
    coada[++ult]=nod;
    while(pr<=ult)
    {
        nod=coada[pr];
        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;
                }
                coada[++ult]=edges[neighbors[nod][i]].dst;
            }
        }
        pr++;
    }
}