#include <fstream>
using namespace std;
ifstream t("dijkstra.in");
ofstream o("dijkstra.out");
int m,n,i,j,p,x,s,y,c[10005][10005],d[10005],tata[10005];
void bellman_ford(int x0)
  {
    int ok,i,j,k;
    for (i=1;i<=n;i++)
      {tata[i]=0; d[i]=2100000000;}
    d[x0]=0;
    for (i=1;i<=n;i++)
      {
        ok=0;
        for (j=1;j<=n;j++)
          for (k=1;k<=n;k++)
            if (d[j]!=2100000000 && c[j][k]!=2100000000)
              if (d[k]>d[j]+c[j][k])
                {
                  d[k]=d[j]+c[j][k];
                  tata[k]=j;
                  ok=1;
                }
      }
    if (ok) o<<"Circuit negativ!";
  }
int main(void)
  {
    t>>n>>m;
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        c[i][j]=2100000000;
    for (i=1;i<=m;i++) {t>>x>>y>>p; c[x][y]=p;};
    bellman_ford(1);
    for (i=2;i<=n;i++) o<<d[i]<<' ';
  }