#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <climits>

#define edge pair< int, int >

using namespace std;


ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
    
vector< pair< int, edge > > GRAPH, MST, gr;

void printArr(int dist[], int n)
{
    for (int i = 2; i <= n; ++i)
       fout << dist[i] << " " ;
}


void BellmanFord(int src, int V, int E)
{
   
    int dist[V + 1];
 
    // Step 1: Initialize distances from src to all other vertices
    // as INFINITE
    for (int i = 0; i <= V; i++)
        dist[i]   = INT_MAX;
    dist[src] = 0;
 
    // Step 2: Relax all edges |V| - 1 times. A simple shortest 
    // path from src to any other vertex can have at-most |V| - 1 
    // edges
    for (int i = 1; i <= V-1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = GRAPH[j].second.first;
            int v = GRAPH[j].second.second;
            int weight = GRAPH[j].first;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
 
    // Step 3: check for negative-weight cycles.  The above step 
    // guarantees shortest distances if GRAPH doesn't contain 
    // negative weight cycle.  If we get a shorter path, then there
    // is a cycle.
    for (int i = 0; i < E; i++)
    {
        int u = GRAPH[i].second.first;
        int v = GRAPH[i].second.second;
        int weight = GRAPH[i].first;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
            {
            	fout << "Ciclu negativ!";
            	return;
            }
    }
 
    printArr(dist, V);
 
    
}

int main()
{
	int i, u, v, w, n, m;

    

    fin >> n >> m;
    

    for(i = 0; i < m; i++)
    {
        fin >> u >> v >> w;
        GRAPH.push_back(pair< int, edge >(w, edge(u, v)));
        
    }

    BellmanFord(1, n, m);

	return 0;
}