#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <stdio.h>
using namespace std;
#define INF numeric_limits<int>::max()
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
vector<vector<pair<int,int>>> graf;
int n,m;
vector<int> dist;
void bellman(int source)
{
    dist[1] = 0;
    for (int j = 0; j < graf[source].size(); j++)
    {
        int neighbour = graf[source][j].first;
        int cost = graf[source][j].second;
        dist[neighbour] = cost;
    }
    for (int k = 0; k < n - 2; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < graf[i].size(); j++)
            {
                int neighbour = graf[i][j].first;
                int cost = graf[i][j].second;
                if (dist[neighbour] > dist[i] + cost)
                {
                    dist[neighbour] = dist[i] + cost;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < graf[i].size(); j++)
        {
            int neighbour = graf[i][j].first;
            int cost = graf[i][j].second;
            if (dist[neighbour] > dist[i] + cost)
            {
                out << "Ciclu negativ!\n";
                return;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (i == source)
            continue;
        out << dist[i] << " ";

    }



}
int main()
{
    in >> n >> m;
    graf.resize(n+1);
    dist.resize(n+1, INF);
    for (int i =0; i < m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        graf[x].push_back(make_pair(y,c));
    }
    bellman(1);
    
    
}