#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define oo 1 << 29
using namespace std;

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


int n,m;
int x,y,z;
int D[NMAX];
int i;
vector <pair <int, int>> G[NMAX];
void Citire()
{
 cin >> n >> m;
 for (i = 1; i <= m; i ++)
    {
     cin >> x >> y >> z;
     G[x].push_back(make_pair(y,z));
    }
 for (i =1 ; i <= n ; i ++)
    D[i] = oo;
}

bool inCoada[NMAX];
queue <int> Coada;
int viz[NMAX];

bool BellmanFord(int nodStart)
{
 D[nodStart] = 0;
 inCoada[nodStart] = 1;
 Coada.push(nodStart);
 while (!Coada.empty())
    {
     nodStart = Coada.front();
     Coada.pop();
     inCoada[nodStart] = 0;
     viz[nodStart]++;
     if (viz[nodStart] >= n)
         return 0;
     for (i = 0 ; i < G[nodStart].size(); i++)
        {
         int Vecin = G[nodStart][i].first;
         int Cost = G[nodStart][i].second;
         if (D[Vecin] > D[nodStart] + Cost)
            {
             D[Vecin] = D[nodStart] + Cost;
                if (inCoada[Vecin] == 0)
                    {
                     Coada.push(Vecin);
                     inCoada[Vecin] = 1;
                    }
            }
        }
    }
 return 1;
}

void Afisare()
{
 if (!BellmanFord(1)) cout << "Ciclu negativ!";
 else
    {

     for (i = 2; i <= n; i ++)
            {
             if (D[i] == 1 << 29) cout << 0 << ' ';
             else cout << D[i] <<' ' ;
            }
    }
}

int main()
{
 Citire();
 Afisare();
}