#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

vector < pair <uint16_t , int16_t> > adiacenta[50001];
int32_t distanta[50001];
uint16_t numar_noduri;

bool Parcurgere ()
{
    queue <uint16_t> candidati;
    bool in_stiva[50001] = { };
    uint16_t adaugat[50001] = { };
    candidati.push(1); in_stiva[1] = true; adaugat[1] = 1;
    while (!candidati.empty())
    {
        const uint16_t nod_actual = candidati.front();
        for (auto nod_vecin : adiacenta[nod_actual]) {
            if (distanta[nod_vecin.first] > distanta[nod_actual] + nod_vecin.second)
            {
                distanta[nod_vecin.first] = distanta[nod_actual] + nod_vecin.second;

                if (!in_stiva[nod_vecin.first])
                {
                    candidati.push(nod_vecin.first);
                    in_stiva[nod_vecin.first] = true;

                    if (++adaugat[nod_vecin.first] >= numar_noduri)
                        { return false; }
                }
            }
        }

        in_stiva[nod_actual] = false;
        candidati.pop();
    }

    return true;
}

int main ()
{
    {
        int32_t numar_arce;
        cin >> numar_noduri >> numar_arce;

        uint16_t nod[2]; 
        for (int16_t cost ; numar_arce-- ; )
            { cin >> nod[0] >> nod[1] >> cost; adiacenta[nod[0]].push_back({nod[1] , cost}); }
    }
    
    for (uint16_t indice = 2 ; indice <= numar_noduri ; indice++)
        { distanta[indice] = 1000000000; }

    if (!Parcurgere()) {
        cout << "Ciclu negativ!";
        cout.close(); cin.close();
        return 0;
    }

    for (int indice = 2 ; indice <= numar_noduri ; indice++)
        { cout << distanta[indice] << ' '; }

    cout.close(); cin.close();
    return 0;
}