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

#define maxn 50073
#define infinit 1001 * maxn


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;

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

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

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

    queue <int> coada;

    coada.push(1);
    treceri[1]++;
    cost[1]=0;
    bool ciclu = false;
    while (!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        viz[nod]=false;
        int size = graf[nod].size();

        for (int i=0;i<size;i++)
        {
            int next = graf[nod][i].nod;
            if (cost[next]>graf[nod][i].cost+cost[nod])
            {
                   cost[next]=graf[nod][i].cost+cost[nod];
                   if (!viz[next])
                   {
                       if (treceri[next]==n)
                       {
                           cout << "Ciclu negativ!";
                           cout.close();
                           cin.close();
                           return 0;
                       }
                       else
                       {
                           coada.push(next);
                           viz[next]=true;
                           treceri[next]++;
                       }
                   }
            }
        }
    }

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

    cout.close();
    cin.close();
    return 0;
}