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

using namespace std;

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

#define INF 2e9
#define MAX_N 50001
int viz[MAX_N];
int nodeCosts[MAX_N];

struct zdrang
{
    int cost, directie;
};

vector<zdrang> graf[MAX_N];
queue <int> Q;


bool negativ = false;

void BF(int node, int n)
{
    Q.push(node);
    while(!Q.empty())
    {
        int curr = Q.front();
        Q.pop();

        viz[curr]++;
        if(viz[curr] > n)
        {
            out << "Ciclu negativ!";
            negativ = true;
            return;
        }

        for(auto x : graf[curr])
        {
            if(nodeCosts[curr] + x.cost < nodeCosts[x.directie])
            {
                Q.push(x.directie);
                nodeCosts[x.directie] = nodeCosts[curr] + x.cost;
            }
        }
    }
}

void setGraf()
{
    for(int i = 2; i < MAX_N; ++i)
        nodeCosts[i] = INF;
}

int main()
{
    int n, m, a, b, x;
    in >> n >> m;

    setGraf();

    for(int i = 0; i < m; ++i)
    {
        in >> a >> b >> x;
        graf[a].push_back({x, b});
    }
    BF(1, n);

    if(negativ)
    {
        return 0;
    }

    for(int i = 2; i <= n; ++i)
    {
        out << nodeCosts[i] << " ";
    }
    return 0;
}