#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;

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

const int NMAX = 50000 + 4;
const int INF = 1000000000;

vector <pair <int ,int> > gr[NMAX];
list <int> coada;
int N, M;
int d[NMAX], decateori[NMAX];
bool viz[NMAX];

bool Bellman(int x0)
{
    for (int i = 1; i <= N; ++i) d[i] = INF;

    d[x0] = 0;
    coada.push_back(x0);
    decateori[x0]++;
    viz[x0] = true;
    while (!coada.empty())
    {
        int nod = coada.front();
        coada.pop_front();
        viz[nod] = false;

        for (int i = 0; i < gr[nod].size(); ++i)
        {


            if (d[gr[nod][i].first] > d[nod] + gr[nod][i].second)
            {
                d[gr[nod][i].first] = gr[nod][i].second + d[nod];

                decateori[gr[nod][i].first] ++;

                if (decateori[gr[nod][i].first] > N + 2) {cout << "Ciclu negativ!";return false;}

                if (!viz[gr[nod][i].first])
                {
                    viz[gr[nod][i].first] = true;
                    coada.push_back(gr[nod][i].first);
                }

            }
        }

    }
    return true;

}


int main()
{
fin >> N >> M;
int a, b, c;
for (int i = 1; i <= M; ++i)
{
    fin >>a>>b>>c;
    gr[a].push_back(make_pair (b, c));
   // gr[b].push_back(make_pair (a, c));
}
    if (Bellman(1))
    {
        for (int i =2; i <= N; ++i) fout <<d[i]<<" ";
    }

return 0;
}