#include <bits/stdc++.h>
using namespace std;

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

int n, m;
const int inf = INT_MAX;
vector<vector<pair<int,int>>> graf;  // graful
queue<int> q; // coada
vector<bool> viz; // 1 - daca apare nodul in coada, 0 altfel
vector<int> nrnod; // pentru a afla are ciclu negativ
vector<int> cost;

void citire()
{
    fin >> n >> m;
    graf.resize(n+1);
    viz.resize(n+1);
    nrnod.resize(n+1);
    cost.resize(n+1, inf);
    cost[1] = 0;

    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;

        graf[a].emplace_back(b,c);
    }
}

void bellman()
{
    q.push(1);
    viz[1] = true;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        viz[nod] = false;

        for(auto next : graf[nod]) // first - nodul urmator ------ second - distanta dintre cele doua
        {
            if(cost[next.first] > cost[nod] + next.second)
            {
                cost[next.first] = cost[nod] + next.second;
                if(viz[next.first] != true)
                {
                        q.push(next.first);
                        viz[next.first] = true;
                }

                nrnod[next.first] = nrnod[nod] + 1;
                if(nrnod[next.first] > n)
                {
                    fout << "Ciclu negativ!";
                    exit(0);
                }
            }
        }
    }
}

void afisare()
{
    for(int i = 2; i <= n; i++)
        fout << cost[i] << ' ';
}

int main ()
{
    citire();

    bellman();

    afisare();

    return 0;
}