/*
 * Bellman-Ford Algorithm
 * using C++ STL
 * 
 * Authored by,
 * Vamsi Sangam
 *
 */
 
#include <cstdio>
#include <climits>
#include <vector>
#include <list>
#include <utility>

#include <ctime>
 
using namespace std;

clock_t start = clock();
clock_t end_no_check = clock();
clock_t end_check = clock();

//functia pentru cronometrat
double diffclock( clock_t clock1, clock_t clock2 ) {

        double diffticks = clock1 - clock2;
        double diffms    = diffticks / ( CLOCKS_PER_SEC / 1000 );

        return diffms;
    }
 
// Bellman-Ford Algorithm which takes the Adjacency List, starting vertex,
// and an empty shortestDistances vector as input. It applies the algorithm
// and keeps filling values into shortestDistances which is a reference
// parameter. It returns true if there are no negative edges, and vice-versa.
int bellmanFord(
                    vector< list< pair<int, int> > > adjacencyList, 
                    int noduri,
                    int nodInitial,
                    vector< pair<int, int> > & shortestDistances
               )
{
    list< pair<int, int> >::iterator traverse;
    int i, j, k;
     
    // Initializare
    for (i = 0; i <= noduri; ++i) {
        shortestDistances[i].first = INT_MAX;
        shortestDistances[i].second = -1;
    }
     
    // Setting distance to source = 0
    shortestDistances[nodInitial].first = 0;
    shortestDistances[nodInitial].second = 0;
     
    // The Algorithm that computes Shortest Distances
    for (i = 1; i <= noduri - 1; ++i) {    // RUlea 'noduri - 1' times = O(|V|)
        for (j = 1; j <= noduri; ++j) {    // Runs as many times as the edges = O(|E|)
            // The code ahead basically explores the whole of Adjcency List,
            // covering one edge once, so the runtime of the code in this 
            // block is O(|E|)
             
            traverse = adjacencyList[j].begin();
            
            //verificam fiecare vecil al nodului curent analizat
            while (traverse != adjacencyList[j].end()) {

                if (shortestDistances[j].first == INT_MAX) {
                    // Important...!
                    //traverse = traverse->next;
                    ++traverse;
                    continue;
                }
                 
                // Checking for Relaxation
                if ((*traverse).second + shortestDistances[j].first < 
                                        shortestDistances[(*traverse).first].first) {
                    // Relaxation
                    shortestDistances[(*traverse).first].first = (*traverse).second
                                        + shortestDistances[j].first;
                    shortestDistances[(*traverse).first].second = j;
                }
                 
                ++traverse;
            }
        }
    }
    end_no_check = clock();

    // Checking for Negative Cycles
    for (j = 1; j <= noduri; ++j) {
        traverse = adjacencyList[j].begin();
         
        while (traverse != adjacencyList[j].end()) {
            // Verificam daca s-a ajuns la nod.
            if(shortestDistances[j].first == INT_MAX)
            {
                ++traverse;
                continue;
            }

            // Checking for further relaxation
            if ((*traverse).second + shortestDistances[j].first < 
                                        shortestDistances[(*traverse).first].first) {
                // Negative Cycle found as further relaxation is possible
                end_check = clock();
                return j;
            }
             
            ++traverse;
        }
    }
    end_check = clock();
    return -1;
}
  
int main()
{
    int noduri, muchii, v1, v2, weight;
     
    //printf("Enter the Number of noduri -\n");
    //Citire numar noduri
    scanf("%d", &noduri);
     
    //printf("Enter the Number of edges -\n");
    //Citire numar edges
    scanf("%d", &muchii);
     
    // Adjacency List is a vector of list.
    // Where each element is a pair<int, int>
    // pair.first -> the edge's destination
    // pair.second -> edge's weight
    vector< list< pair<int, int> > > adjacencyList(noduri + 1);
     
    //printf("Enter the edges V1 -> V2, of weight W\n");
     
    for (int i = 1; i <= muchii; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
         
        // Adding Edge to the Directed Graph
        adjacencyList[v1].push_back(make_pair(v2, weight));
    }
     
         
    vector< pair<int, int> > shortestDistances(noduri + 1);
    // shortestDistances is a vector of pairs
    // pair.first -> the shortest distance from start vertex
    // pair.second -> parent vertex in the shortest path
     
    int nodInitial;
    
    start = clock();

    //printf("\nEnter a Start Vertex -\n");
    //scanf("%d", &nodInitial);
    nodInitial=1;
     
    int returnValue = bellmanFord(adjacencyList, noduri, nodInitial, shortestDistances);
     
    if (returnValue == -1) {
        //printf("Graful nu contine cicluri negative. Se continua rularea\n");
    } else {
        printf("Ciclu negativ!\n");
        return 0;
    }
    //printf("Timpul necesar fara cicluri negative: %lf\n", diffclock(end,start) );
    //printf("Timpul necesar cu posibile cicluri negative: %lf\n", diffclock(end,start) );
     
    //printf("\n\nNod    Distanta minima pana la nodul %d     Nod parinte-\n", nodInitial);
    for (int i = 2; i <= noduri; ++i) {
        //if(shortestDistances[i].first != INT_MAX)
        //    printf("%d \t  %d \t\t\t\t    %d\n", i, shortestDistances[i].first,
         //                                       shortestDistances[i].second);
        //else
        //    printf("%d \t  Inf \t\t\t\t    %d\n", i, shortestDistances[i].second);
        printf("%d ", shortestDistances[i].first);
    }
    printf("\n");
     
    return 0;
}