#include <bits/stdc++.h>

using namespace std;

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

const int dijMax = 50001;

class Graf
{
    int NrNoduri;

public:
    Graf(int NrNoduri);
    int BellmanFord(int nod, vector<pair<int, int>>G[dijMax]);
};

Graf::Graf(int NrNoduri)
{
    this->NrNoduri = NrNoduri;
}

int Graf :: BellmanFord(int nod, vector<pair<int, int>>G[dijMax])
{
    queue <int> coada;
    int Vizitat[dijMax] = {0};
    int distanta[dijMax];
    bool InCoada[dijMax];

    for(int i = 1; i <= NrNoduri; i++)
        distanta[i] = INT_MAX;

    distanta[nod] = 0;
    coada.push(nod);
    InCoada[nod] = 1;

    while(!coada.empty())
    {
        int nodcurent = coada.front();
        Vizitat[nodcurent]++;

        if(Vizitat[nodcurent] >= NrNoduri)
        {
            out <<"Ciclu negativ!";
            return 0;
        }

        coada.pop();
        InCoada[nodcurent] = 0;

        for(int i = 0; i < G[nodcurent].size(); i++)
        {
            int vecin = G[nodcurent][i].first;
            int cost = G[nodcurent][i].second;

            if(distanta[nodcurent] + cost < distanta[vecin])
            {
                distanta[vecin] = distanta[nodcurent] + cost;
                if(!InCoada[vecin])
                    coada.push(vecin);
            }
        }
    }

    for(int i = 2; i <= NrNoduri; i++)
        out << distanta[i] << " ";

    return 0;

}

int main()
{
    int N, M;
    int nod1, nod2, cost;
    vector <pair<int, int>>G[dijMax];

    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        in >> nod1 >> nod2 >> cost;
        G[nod1].push_back(make_pair(nod2, cost));
    }

    Graf g(N);
    g.BellmanFord(1, G);

    return 0;
}