#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

#define NMAX 50001
#define INF 2000000000

using namespace std;

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

    int n, m, x, y, c;
    int cost[NMAX], ap[NMAX];

    vector <pair <int, int> > v[NMAX];

    f >> n >> m;

    for (int i = 0; i < m; i++){

        f >> x >> y >> c;

        v[x].push_back(make_pair(y, c));
        //v[y].push_back(make_pair(x, c));
    }

    bitset <NMAX> in_queue;
    priority_queue <pair <int, int>> q;

    q.push(make_pair(0,1));

    in_queue[1] = 1;
    for (int i = 2; i <= n; i++)
        in_queue[i] = 0;


    cost[1] = 0;
    for (int i = 2; i <= n; i++)
        cost[i] = INF, ap[i] = 0;

    while(q.empty() == 0) {

            //for (int i = 2; i <= n; i++)
                //g << cost[i] << " ";
            //g << '\n';

            int node = q.top().second;

            q.pop();
            in_queue[node] = 0;

            for (auto it : v[node])
                if (cost[node] + it.second < cost[it.first]) {
                    cost[it.first] = cost[node] + it.second;
                    ap[it.first]++;

                    if (ap[it.first] == n){
                        g << "Ciclu negativ!\n";
                        return 0;
                    }

                    if (in_queue[it.first] == 0) {
                        q.push(make_pair(-cost[it.first], it.first));
                        in_queue[it.first] = 1;
                    }
                }
    }

    for (int i = 2;i <= n; i++)
        g << cost[i] << " ";

    f.close();
    g.close();

    return 0;
}