#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define inf 1<<30
#define nmax 50010

using namespace std;

struct vecini
{
    int vec,cost;
};

vector<vecini> v[nmax];
int n,m,prezent[nmax],cost[nmax],nrviz[nmax],ok=1;

void citire()
{
    vecini aux;
    int i,x,y,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&c);
            aux.vec=y;
            aux.cost=c;
            v[x].push_back(aux);
        }

}

void bellman()
{
    int c,i;
    queue<int> q;
    q.push(1);
    int p;
    while(!q.empty())
          {
              p=q.front();
              q.pop();
              prezent[p]=0;
              for(i=0;i<v[p].size();i++)
                  {
                      c=cost[p]+v[p][i].cost;
                      if(c<cost[v[p][i].vec])
                         {
                          nrviz[v[p][i].vec]++;
                          cost[v[p][i].vec]=c;
                          if(nrviz[v[p][i].vec]>n)
                             {
                                 printf("Ciclu negativ!");
                                 ok=0;
                                 return;
                             }
                          if(!prezent[v[p][i].vec])
                             {
                                 q.push(v[p][i].vec);
                                 prezent[v[p][i].vec]=1;
                             }
                          }
                  }
          }
}

void afisare()
{
    for(int i=2;i<=n;i++)
        printf("%d ",cost[i]);
}

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

    citire();
    prezent[1]=nrviz[1]=1;
    for(int i=1;i<=n;i++)
        cost[i]=inf;
    cost[1]=0;
    bellman();
    if(ok)
      afisare();

    return 0;
}