#include <fstream>
#include <vector>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int inf=1<<30;
const int MAXN=50001;

struct muchii
{
    int x;
    int c;
};

vector <muchii> M[MAXN];
int n,m;
int cost[MAXN], viz[MAXN],coada[2*250001];

void bf()
{
    int p,u,i,y,nod;
    p=0;
    u=1;
    viz[1]=1;
    coada[u]=1;
    for(i=2;i<=n;i++)
      cost[i]=inf;
    while(p!=u)
    {
        p++;
        y=coada[p];
        for(i=0;i<M[y].size();i++)
        {
          nod=M[y][i].x;
          if(cost[y]+M[y][i].c<cost[nod])
          {
              cost[nod]=cost[y]+M[y][i].c;
              if(viz[nod]>n && cost[nod]<0)
               {
                   g<<"Ciclu negativ!";
                   return;
               }
             viz[y]++;
             u++;
             coada[u]=nod;
          }
        }
    }
        for(int i=2;i<=n;i++)
    {
        if(cost[i]==inf)g<<"0\n";
        else
        g<<cost[i]<<" ";
    }
}
int main()
{
    muchii aux;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int p,q,k;
        f>>p>>q>>k;
        aux.x=q;
        aux.c=k;
        M[p].push_back(aux);
    }
    bf();

    return 0;
}