#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#define Nmax 50005
#define pii pair<int,int>
#define add push_back
#define inf 0x3f3f3f3f

using namespace std;
int n, m, exista_ciclu, nr[Nmax], d[Nmax];
vector <pii> v[Nmax];
queue <int> q;
bitset <Nmax> viz;

void Citire()
{
   int i, x, y, c;
   scanf("%d %d", &n, &m);
   for (i=1; i<=m; i++)
   {
      scanf("%d %d %d", &x, &y, &c);
      v[x].add(make_pair(c, y));
   }
}

void Bellman()
{
   int x;
   q.push(1);
   memset(d, inf, sizeof(d));
   d[1]=0;
   while (!q.empty())
   {
      x=q.front();
      q.pop();
      viz[x]=0;
      if (++nr[x]>=n)
      {
         exista_ciclu=1;
         break;
      }
      for (vector<pii>::iterator it=v[x].begin(); it!=v[x].end(); ++it)
         if (!viz[it->second] && d[it->second]>d[x]+d[it->first])
         {
            viz[it->second]=1;
            d[it->second]=d[x]+it->first;
            q.push(it->second);
         }
   }
}

void Afisare()
{
   int i;
   for (i=2; i<=n; i++)
      printf("%d ", d[i]);
}

int main()
{
   freopen("bellmanford.in", "r", stdin);
   freopen("bellmanford.out", "w", stdout);
   Citire();
   Bellman();
   if (exista_ciclu)
   {
      printf("Ciclu negativ!");
      return 0;
   }
   Afisare();

   return 0;
}