#include<stdio.h>
#include<string.h>
#include<vector>
#define MAXV 50000
#define MAXE 250000
#define INF 1000000000
#define MASK 65535
struct Edge
{
    int dst;
    int cost;
};
void init();
void blf(int nod);
FILE*fin,*fout;
std::vector<int> neighbors[MAXV];
Edge edges[MAXE];
int visited[MAXV];
bool in_queue[MAXV];
int shortestPath[MAXV];
int coada[MASK+1];
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();
    blf(0);
    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)&MASK]=nod;
    in_queue[nod]=1;
    while(pr<=ult && ok)
    {
        nod=coada[pr];
        for(int i=0; i<neighbors[nod].size(); i++)
        {
            if(shortestPath[edges[neighbors[nod][i]].dst]>shortestPath[nod]+edges[neighbors[nod][i]].cost)
            {
                visited[edges[neighbors[nod][i]].dst]++;
                shortestPath[edges[neighbors[nod][i]].dst]=shortestPath[nod]+edges[neighbors[nod][i]].cost;
                if(visited[edges[neighbors[nod][i]].dst]==V)
                {
                    ok=0;
                }
                if(!in_queue[edges[neighbors[nod][i]].dst])
                {
                    coada[(++ult)&MASK]=edges[neighbors[nod][i]].dst;
                    in_queue[edges[neighbors[nod][i]].dst]=1;
                }
            }
        }
        pr++;
        in_queue[nod]=0;
    }
}