#include <bits/stdc++.h>
#define NM 50010
using namespace std;
const int inf = 0x3f3f3f3f;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int cst[NM],fcv[NM];
bool ok;
//vector costuri, vector frecventa

vector <pair<int,int>>v[NM]; //lista adiacenta + cost
void bell(int n)
{
 queue <int> q;//coada evidenta noduri tata
 // adaug in coada nodul de inceput-1
 q.push(1);
  while(!q.empty())
    {
       int x=q.front();
        q.pop();//il scoatem cand relaxam muchiile aferente lui
        for(int i=0;i<v[x].size();i++)
        {
           int y=v[x][i].first;
            if(cst[y]>cst[x]+v[x][i].second)
            {

// pt fiecare vecin al nodului curent se actualizeaza costul minim
                cst[y]=cst[x]+v[x][i].second;
                q.push(y);
                fcv[y]++;
//nu există cicluri negative ⇔ nu se mai fac actualizări la pasul n

                if(fcv[y]>=n)
                 {  ok=1;
                    g<<"Ciclu negativ!";
                    //cout<<"ciclu negativ";
                 }

            }
        }
    }
}

int main()
{
    int n,m;
    f>>n>>m;
   //cin>>n>>m;
 //citesc in ordine valorile si in v[x](nodul tata) se adauga perechile (nod(fiu), cst) in liste de adiacenta
    for(int i=1;i<=m;i++)
    { int x,y,c;
        f>>x>>y>>c;
        //cin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
//setez cu inf vectorul de costuri
    for(int i=2;i<=n;i++)
        cst[i]=inf;

      bell(n);

    // Afisare daca nu exista costuri negative

    if(ok==0)
    for( int i=2;i<=n;i++)
        {  g<<cst[i]<<" ";
           //cout<<cst[i]<<" ";
        }

    return 0;
}