#include <iostream>
#include<vector>
#include<queue>
#include<cstdio>

#define maxn 50073
#define infinit 1<<30


using namespace std;

int cost[maxn],n,m,treceri[maxn];
bool viz[maxn];

typedef struct
{
 int nod;
 int cost;
}pereche;

vector <pereche> graf[maxn];

void inserare(int nod1,int nod2,int cost)
{
    pereche p;
    p.nod=nod2;
    p.cost=cost;

    graf[nod1].push_back(p);
}



int main()
{
    int x,y,c;

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

    cin>>n>>m;

    for (int i=1;i<=m;i++)
        {
            cin>>x>>y>>c;
            inserare(x,y,c);
        }

    fill(cost,cost+n+1,infinit);
    fill(treceri,treceri+n+1,false);

    queue <int> coada;

    coada.push(1);
    treceri[1]++;
    cost[1]=0;

    while (!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        viz[nod]=false;
        for (unsigned int i=0;i<graf[nod].size();i++)
            if (cost[graf[nod][i].nod]>graf[nod][i].cost+cost[nod])
            {
                   cost[graf[nod][i].nod]=graf[nod][i].cost+cost[nod];
                   if (!viz[graf[nod][i].nod])
                   {
                       if (treceri[graf[nod][i].nod]==n)
                       {
                           printf("Ciclu negativ!");
                           return 0;
                       }
                       else
                       {
                           coada.push(graf[nod][i].nod);
                           viz[graf[nod][i].nod]=true;
                           treceri[graf[nod][i].nod]++;
                       }
                   }
            }
    }

    for (int i=2;i<=n;i++)
        cout<<cost[i]<<" ";



    return 0;
}