#include<fstream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int NMAX=50005;
int m,n,d[50005],c[10000][10000],viz[NMAX],  tata[NMAX];;
void citire ()
{
	ifstream f("dijkstra.in");
	f>>n>>m;
	int x,y,C,i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			c[i][j]=INF;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>C;
		c[x][y]=C;
	}
	f.close();
}
int bellman_ford(int x0) 
{
   int ok, i, j, k;
   for (i=1;i<=n;i++) {
      tata[i] = 0; d[i] = INF;}
   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]!=INF && c[j][k]!=INF)
               if (d[k]>d[j]+c[j][k])
               {
                  d[k] = d[j]+c[j][k];
                  tata[k] = j;
                  ok = 1;
               }
   } 
   if (ok == 1) {}
   return ok;
}

void scrie()
{
	ofstream g("dijkstra.out");
	int i;
	for(i=2;i<=n;i++)
		g<<d[i]<<' ';
	g.close();
}
int main ()
{
	citire();
	bellman_ford(1);
	scrie();
	return 0;
}