#include <fstream>
#include <vector>
#define nmax 50001
#define inf 200000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct arc{int y, c;};
vector <arc> lista[nmax];
int n,m,start=1;
bool viz[nmax];
int cmin[nmax];
int pre[nmax];

void citire();
void DIJ();
void afisare();

int main()
{
    citire();
    DIJ();
    afisare();
    return 0;
}
void citire()
{
   int i,n1,n2,ct;
   arc aux;
   fin>>n>>m;
   for (i=1; i<=m; i++)
      {
         fin>>n1>>n2>>ct;
         aux.y=n2;
         aux.c=ct;
         lista[n1].push_back(aux);
      }
}
void DIJ()
{
   int i,j,lgmin=inf,vfmin;
   for (i=1; i<=n; i++)
      {
         if (i!=start)
            {cmin[i]=inf;
             pre[i]=start;
            }
         else {
               cmin[i]=0;
               pre[i]=0;
            }
      }
   for (i=0; i<lista[start].size(); i++)
      {
         cmin[lista[start][i].y]=lista[start][i].c;
         pre[lista[start][i].y]=start;
         }
   viz[start]=1;
   for (i=1; i<n; i++)
      {  lgmin=inf;
         for (j=1; j<=n; j++)
            if (!viz[j] && cmin[j]<lgmin)
               {
                  lgmin=cmin[j];
                  vfmin=j;
               }
         viz[vfmin]=1;
         for (j=0; j<lista[vfmin].size(); j++)
            if (!viz[lista[vfmin][j].y] && lgmin+lista[vfmin][j].c<cmin[lista[vfmin][j].y])
               {cmin[lista[vfmin][j].y]=lgmin+lista[vfmin][j].c;
                pre[lista[vfmin][j].y]=vfmin;
               }
      }
}
void afisare()
{
   int i,j,afis[nmax];
   for (i=1; i<=n; i++)
         if (i!=start)
            {if (cmin[i]!=inf)
               fout<<cmin[i]<<' ';
            else fout<<0<<' ';
            }
}