#include <bits/stdc++.h>

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");

//#define fin std::cin 
//#define fout std::cout 

const int NMAX = 1e5 + 5;
const int inf = 1e9;

int n, m;
std::vector<std::pair<int, int>> G[NMAX];

int dist[NMAX];
bool in_queue[NMAX];
int relaxed[NMAX];

void bellman_ford(int ref_node)
{
    for(int i = 1; i <= n; ++i)
        dist[i] = inf;

    dist[ref_node] = 0;
    in_queue[ref_node] = true;
    relaxed[ref_node] = 1;

    std::queue<int> q;
    q.push(ref_node);

    while(!q.empty())
    {
        int node = q.front();
        
        in_queue[node] = false;
        q.pop();

        for(auto pair : G[node])
        {
            int adj = pair.first;
            int cost = pair.second;

            if(dist[adj] > dist[node] + cost)
            {
                dist[adj] = dist[node] + cost;
                
                if(!in_queue[adj])
                {
                    in_queue[adj] = true;
                    relaxed[adj]++;
                    
                    if(relaxed[adj] >= n) // ciclu de cost negativ daca un nod este relaxat de mai mult de N - 1 ori
                    {
                        fout << "Ciclu negativ!\n";
                        std::exit(0);
                    }

                    q.push(adj);
                }
            }
        }
    }

    for(int node = 1; node <= n; ++node)
        if(node != ref_node)
            fout << dist[node] << " ";
}

int main() 
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        G[x].push_back({y, cost});
    }

    int ref_node = 1;

    bellman_ford(ref_node);

    return 0;
}