#include <iostream>
#define inf 1000000000
#include <fstream>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
long x[22000][22000], n , m, t[50000], d[50000];
void bellman_ford (int k)
{int i, j, l;
 for (i=1;i<=n;i++)
     {t[i]=0;
      d[i]=inf;
     }
 d[k]=0;
 for (l=1;l<=n;l++)
      {
       for (i=1;i<=n;i++)
             for (j=1;j<=n;j++)
                if(d[i]!=inf && x[i][j]!=inf)
                   if(d[j]>d[i]+x[i][j])
                      {d[j]=d[i]+x[i][j];
                      t[j]=i;
                      }
      }
}
int main()
{fin >> n >> m ;
 int a, b, c;
 for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
          if(i!=j)x[i][j]=inf;
 for (int i=1;i<=m;i++)
    {fin >> a >> b >> c;
     x[a][b]=c;
    }
    fin.close ();
bellman_ford(1);
for (int i=2;i<=n;i++)
     fout << d[i] << " ";
fout.close ();
    return 0;
}