#include <stdio.h>
#include <vector>
#include <deque>
#define siz 50005
#define inf 0x3f3f

using namespace std;

struct int1
{
    int nod,cos;
}x;

vector <int1> V[siz];
deque <int> Q;
int n,m,cnt[siz];
int cost[siz];
int viz[siz];

void citire()
{
    int a;
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d %d",&a,&x.nod,&x.cos);
        V[a].push_back(x);
    }
}

void solve()
{
    for (int i=1;i<=n;i++)
        cost[i]=inf;
    cost[1]=0;
    Q.push_back(1);
    int top,Cost;
    while (!Q.empty())
    {
        top=Q.front();
        Cost=cost[top];
        cnt[top]++;
        if (cnt[top]>=m)
        {
            printf("Ciclu negativ!\n");
            return ;
        }
        Q.pop_front();
        viz[top]=0;
        for (int i=0;i<V[top].size();i++)
            if (cost[V[top][i].nod]>Cost+V[top][i].cos)
            {
                cost[V[top][i].nod]=Cost+V[top][i].cos;
                if (!viz[V[top][i].nod])
                {
                    viz[V[top][i].nod]=1;
                    Q.push_back(V[top][i].nod);
                }
            }
    }
    for (int i=2;i<=n;i++)
        printf("%d ",cost[i]);
}

int main ()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);
    citire();
    solve();
    return 0;
}