#include <fstream>
#include <vector>


using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int nMAX = 50001;
const int mMAX = 250000;
const int INFINIT = 1 << 30;

struct muchie {
    int u, v, c;
};

vector <muchie> vmuchii(0);
int n, m, dist[nMAX];
bool eCicluNegativ = false;

void bellmanford(int nod)
{
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INFINIT;//pt fiecare nod de la 1 la n, initializam distanta cu infinit
    }
    dist[nod] = 0;


// relaxari succesive
// cum in initializare se face o relaxare (daca exista drum direct de la sursa la nod => 
// dist[v] = dist[u,v]) mai sunt necesare |n-1| relaxari 
    for (int nrtimes = 1; nrtimes <= n-1; nrtimes++)
      for (int muchiei = 0; muchiei < m; muchiei++)
        {
            if ((dist[vmuchii[muchiei].u] + vmuchii[muchiei].c) < dist[vmuchii[muchiei].v])
                dist[vmuchii[muchiei].v] = dist[vmuchii[muchiei].u] + vmuchii[muchiei].c;
        }

    //daca inca se mai pot relaxa muchii
     for (int muchiei = 0; muchiei < vmuchii.size(); muchiei++)
     {
         if ((dist[vmuchii[muchiei].u] + vmuchii[muchiei].c) < dist[vmuchii[muchiei].v])
         {
             g << "Ciclu negativ!";
             eCicluNegativ = true;
             break;
         }
      }

     if (eCicluNegativ == true)
     {//NOOP;
     }
     else
     {
         for (int i = 2; i <= n; i++)
             if (dist[i] == INFINIT)
                 g << 0 << ' ';
             else
                 g << dist[i] << ' ';
     }
    f.close();
    g.close();
}

void citire_muchii(int m) {
    int u, v, c;
    for (int i = 0; i < m; i++) {
        f >> u >> v >> c;
        muchie muc;
        muc.u = u; muc.v = v; muc.c = c;
        vmuchii.push_back(muc);
    }
}

int main()
{
    f >> n >> m;
    citire_muchii(m);
    bellmanford(1);
	return 0;
}