#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int sz = (int)5e4+1;
const int infinity = (1<<30)-1;

bool BellmanFord(int startNode);

FILE *in,*out;

int nodes, edges;
int visitedTimes[sz];
vector <pair<int, int> > graph[sz];
vector <int> dist(sz, infinity);
bool visited[sz];

int main()
{
    in=fopen("bellmanford.in","rt");
    out=fopen("bellmanford.out","wt");

    fscanf(in,"%d%d",&nodes,&edges);
    int rFrom, rTo, rCost;
    for(int i=1; i<=edges; ++i)
    {
        fscanf(in,"%d%d%d",&rFrom,&rTo,&rCost);
        graph[rFrom].push_back(make_pair(rTo,rCost));
    }

    if(BellmanFord(1))
    {
        for(int i=2; i<=nodes; ++i)
            fprintf(out,"%d ",dist[i]);
        fprintf(out,"\n");
    }
    else
        fprintf(out,"Ciclu negativ!");

    fclose(in);
    fclose(out);
    return 0;
}

bool BellmanFord(int startNode)
{
    dist[startNode] = 0;
    queue <int> myQ;
    myQ.push(startNode);



    while(!myQ.empty())
    {
        int current = myQ.front();
        myQ.pop();

        vector <pair<int,int> >::iterator it, end = graph[current].end();
        for( it=graph[current].begin(); it!=end; ++it)
            if(dist[it->first] > dist[current] + it->second)
            {
                dist[it->first] = dist[current] + it->second;
                if(!visited[it->first])
                {
                    //visitedTimes[it->first]++;
                    if(++visitedTimes[it->first] > nodes)
                        return false;
                    myQ.push(it->first);
                    visited[it->first] = true;
                }

            }
        visited[current] = false;
    }
    return true;

}