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

#define NMAX 50005
#define oo 1 << 30
using namespace std;

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

int n,m,i,j;
int p;
int x,y,z;
vector <pair <int, int> > G[NMAX];
int D[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;
}

struct compara
{
 bool operator() (int x, int y)
    {
     return D[x] > D[y];
    }
};


bool InCoada[NMAX];
queue <int> Coada;
int viz[10001];
bool Dijkstra(int nodStart)
{
 D[nodStart] = 0;
 InCoada[nodStart] = 1;
 Coada.push(nodStart);

 while (!Coada.empty())
    {
     nodStart = Coada.front();
     InCoada[nodStart] = 0;
     Coada.pop();
    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])
                        {
                         InCoada[Vecin] = true;
                         Coada.push(Vecin);
                        }
                    }
        }
    }
 return 1;
}

void Afisare()
{
 if (!Dijkstra(1)) cout << "Ciclu negativ!";
 else{
    for (i = 2; i <= n; i ++)
        if (D[i] == 1 << 30) cout << 0 << ' ';
        else cout << D[i] << ' ';

    }
}


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