#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

#define Nmax 50002
#define inf 0x3f3f3f
#define nod first
#define cost second

using namespace std;

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

int n, m, i, j, x, y, c, D[Nmax], ItNod[Nmax], Nod, start;
bool fv[Nmax];

vector <pair <int, int> > G[Nmax];
vector <pair <int, int> > :: iterator it;
queue <int> Q;

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

    memset(D, inf, sizeof(D));
    D[1] = 0;
    memset(ItNod, 0, sizeof(ItNod));
    Q.push(1);
    fv[1] = 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] <<" ";
    }

    fin.close();
    fout.close();
    return 0;
}