#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 50001
#define INF 0x3f3f3f3f
#define nod first
#define cost second
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

vector < pair < int, int > > G[NMAX];
vector < pair < int, int > >::iterator it;
queue < int > Q;
int n, m, i, x, y, c, d[NMAX],ItNod[NMAX], Nod, start;
bool fv[NMAX];

int main()
{
    fin >> n >> m;
    while (m)
    {
        fin >> x >> y >> c;
        G[x].push_back ( make_pair ( y, c ) );
        m--;
    }

    memset (fv, false, sizeof (fv));
    memset (d, INF, sizeof (d));

    start = 1;
    d[start] = 0;
    memset (ItNod, 0, sizeof (ItNod));
    Q.push (start);
    fv[start] = true;

    while (!Q.empty ())
    {
        Nod = Q.front ();
        fv[Nod] = false;

        for (it = G[Nod].begin (); it != G[Nod].end (); it++)
        {
            if (d[(*it).nod] > d[Nod] + (*it).cost)
                {
                    d[(*it).nod] = d[Nod] + (*it).cost;

                    if (!fv[(*it).nod])
                    {
                        Q.push ((*it).nod);
                        fv[(*it).nod] = true;

                        if (++ItNod[(*it).nod] > n)
                        {
                            fout << "Ciclu negativ!";
                            return 0;
                        }
                    }
                }
        }
        Q.pop ();
    }

    for (i = 2; i <= n; i++)
        fout << d[i] << " ";

    return 0;
}