#include <bits/stdc++.h>

using namespace std;

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

struct edge{
    int v, c;
};

const int max_n = (int)5e4 + 5;
const int inf = (int)1e9 + 7;

vector<edge> g[max_n];

vector<int> times(max_n);

vector<int> dist(max_n, inf);

int main()
{
    int n, m; fin >> n >> m;

    for(int i = 1; i <= m; ++i)
    {
        int u, v, c; fin >> u >> v >> c;
        g[u].push_back({v , c});
    }
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if(times[u] > n)
        {
            fout << "Ciclu negativ!";
            return 0;
        }
        for(edge ed : g[u])
        {
            int v = ed.v, c = ed.c;
            if(dist[v] > dist[u] + c)
            {
                dist[v] = dist[u] + c;
                q.push(v);
                times[v] += 1;
            }
        }
    }
    for (int i = 2; i <= n; ++i){
        fout << dist[i] << " ";
    }
    return 0;
}