#include <stdio.h>
#include <string.h>
#include <deque>
#include <vector>
#include <algorithm>
#include <utility>

#define pii pair< int,int >
#define st first
#define nd second

using namespace std;

const int Mn = 50005;
const int oo = 1 << 30;

int N,M,pos = 0;
int dst[Mn],cnt[Mn];
bool used[Mn];
char buff[Mn];

deque< int > dq;
vector< pii > G[Mn];

void read(int &num)
{
    num = 0;
    char sign = '+';

    while (!isdigit(buff[pos]))
    {
        sign = buff[pos];

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    while (isdigit(buff[pos]))
    {
        num = num * 10 + buff[pos] - '0';

        if (++pos == Mn)
           fread(buff,1,Mn,stdin),pos = 0;
    }

    if (sign == '-')
       num *= -1;
}

bool bellmanford()
{
    for (int i = 2;i <= N;i++)
        dst[i] = oo;

    dst[1] = 0;
    dq.push_back(1);
    used[1] = 1;

    while (!dq.empty())
    {
        int node = dq.front();

        dq.pop_front();
        used[node] = 0;

        for (int i = 0;i < G[node].size();i++)
        {
            int x = G[node][i].st,
                y = G[node][i].nd;

            if (dst[node] + y < dst[x])
            {
                dst[x] = dst[node] + y;

                if (!used[x])
                {
                    if (cnt[x] > N)
                       return 0;

                    dq.push_back(x);
                    used[x] = 1;
                    cnt[x]++;
                }
            }
        }
    }
    return 1;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

     read(N);
     read(M);

     for (;M;M--)
     {
         int a,b,c;
         read(a);
         read(b);
         read(c);
         G[a].push_back(make_pair(b,c));
     }

     if (!bellmanford())
         printf("Ciclu negativ!\n");
   else
     {
         for (int i = 2;i <= N;i++)
             printf("%d ",dst[i]);

         printf("\n");
     }

  return 0;
}