#include <vector>
#include <climits>
#include <iostream>
#include <fstream>
#define inf INT_MAX
#define nmax 50001
using namespace std;
int n;
vector <pair <int, int> > v[nmax];
vector <int> cost (nmax, inf);
vector <int> coada;
int viz[nmax];
ofstream g("bellmanford.out");
int nr[nmax];
bool bf ()
{
    cost[1]=0;
    nr[1]++;
    coada.push_back(1);
    int x, vf, gr, pr=0;

    while (pr<coada.size())
    {
        x=coada[pr];
        viz[x]=0;
        vector <pair <int ,int > > :: iterator it;
        for (it=v[x].begin();it!=v[x].end();++it)
        {
          vf=(*it).first;
          gr=(*it).second;
          if (cost[vf] > cost[x]+gr)
          {
              cost[vf]=cost[x]+gr;
              nr[vf]++;
              if (nr[vf] > n+2) {g << "Ciclu negativ!"; return 0;}
              if (!viz[vf])
              {
                  viz[vf]=1;
                  coada.push_back(vf);
              }
          }
        }
        pr++;

    }
     return 1;
}
int main()
{
    ifstream f("bellmanford.in");

    int m,i, x, y, c;
    f >> n >>m;
    for (i=1; i<=m; ++i)
    {
        f >> x >> y >> c;
        v[x].push_back(make_pair(y,c));
    }

    if (bf())
        for (i=2; i<=n; ++i)
        g << cost[i] << " ";
    return 0;
}