#include <bits/stdc++.h>
#define nmax 50003
#define infinity 2000000000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
struct graf{
    int destinatie, cost;
};
int n, m, distante[nmax];
bool incoada[nmax];
int contor[nmax];
vector <graf> graphs[nmax];
queue <int> coada;

void bellmanford()
{
    int i, j, nod;
    for(i = 2; i <= n; i++)
        distante[i] = infinity;
    coada.push(1);
    incoada[1] = 1;
    while(!coada.empty())
    {
        nod = coada.front();
        contor[nod]++;
        if(contor[nod] == n)
        {
            fout << "Ciclu negativ!";
            return;
        }
        for(j = 0; j < graphs[nod].size(); j++)
        {
            if (distante[graphs[nod][j].destinatie] > distante[nod] + graphs[nod][j].cost)
            {
                distante[graphs[nod][j].destinatie] = distante[nod] + graphs[nod][j].cost;
                if(!incoada[graphs[nod][j].destinatie])
                    coada.push(graphs[nod][j].destinatie), incoada[graphs[nod][j].destinatie] = 1;
            }
        }
        coada.pop();
        incoada[nod] = 0;
    }
    for(i = 2; i <= n; i++)
        fout << distante[i] << ' ';
}


int main()
{
    graf x;
    int a, b, c, i;
    fin >> n >> m;
    for(i = 0; i < m; i++)
    {
        fin >> a >> b >> c;
        x.destinatie = b, x.cost = c;
        graphs[a].push_back(x);
    }
    bellmanford();









    return 0;
}