#include <fstream>
#include <vector>
#define NMAX 50002
#define INF 100000000000ll
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct varf {int x, c;};
int n, x0=1;
vector<varf> G[NMAX]; ///liste de adiacenta cu costuri
bool uz[NMAX];
long long int cmin[NMAX];
int H[NMAX]; ///aici retin varfurile organizate ca un heap dupa CMIN
int nr;
int poz[NMAX];
///poz[x]=0 daca x nu e in heap;
/// pozitia pe care se afla in heap x
void upgrade(int H[], int n, int poz);
void inserare(int H[], int &n, int x);
void combinare(int H[], int n, int poz);
int ExtrageMin(int H[], int &n);
void citire();
void dijkstra();
void afisare();
int main()
{
 citire();
 dijkstra();
 afisare();
 return 0;
}

void citire()
{int i, j, c, m;
 varf aux;
 fin>>n>>m;
 while (fin>>i>>j>>c)
       {
        ///in lista de adiacenta a lui i trebuie sa adaug (j,c)
        aux.x=j; aux.c=c;
        G[i].push_back(aux);
       }
  for (i=1; i<=n; i++) cmin[i]=INF;
  cmin[x0]=0;
  H[1]=x0; nr=1; poz[x0]=1;
}

void dijkstra()
{int i, j, vfmin, x, cost;
 for (i=1; i<=n; i++)
     {///calculez vfmin
      vfmin=ExtrageMin(H,nr);
      if (cmin[vfmin]==INF) return;
       ///selectez vfmin
       uz[vfmin]=1;
       ///optimizez eventual costurile minime
       for (j=0; j<G[vfmin].size(); j++)
            {
             x=G[vfmin][j].x; cost=G[vfmin][j].c;
             if (!uz[x] && cmin[x]>cmin[vfmin]+cost)
                {  cmin[x]=cmin[vfmin]+cost;
                  ///upgrade
                  ///promovez varful x in Heap pana ajunge la pozitia corecta
                  if (poz[x]) upgrade(H,nr,poz[x]);
                     else inserare(H,nr,x);
                }
            }
     }
}
void afisare()
{int i;
 for (i=2; i<=n; i++)
     if (cmin[i]==INF) fout<< 0<<' ';
        else fout<<cmin[i]<<' ';
 fout<<'\n';
}


void inserare(int H[], int &n, int x)
{int fiu, tata;
 fiu=n+1; tata=fiu/2;
 while (tata && cmin[H[tata]]>cmin[x])
       {
        H[fiu]=H[tata]; poz[H[tata]]=fiu;
        fiu=tata;
        tata=fiu/2;
       }
 H[fiu]=x; n++; poz[x]=fiu;
}

void combinare(int H[], int n, int ppoz)
///combina H[poz] cu heap-urile (corecte!) cu radacinile pe pozitiile 2poz si 2poz+1
{int x=H[ppoz], fiu, tata;
 tata=ppoz; fiu=2*tata;
 while (fiu<=n)
       {
        if (fiu+1<=n && cmin[H[fiu+1]]<cmin[H[fiu]]) fiu++;
        if (cmin[H[fiu]]>=cmin[x]) break;
        H[tata]=H[fiu]; poz[H[fiu]]=tata;
        tata=fiu;
        fiu=2*tata;
       }
 H[tata]=x; poz[x]=tata;
}

int ExtrageMin(int H[], int &n)
{int minim=H[1];
 H[1]=H[n]; n--;
 combinare(H,n,1);
 return minim;
}

void upgrade(int H[], int n, int ppoz)
{int fiu=ppoz, tata=fiu/2, aux;
 while (tata)
       {
         if (H[fiu]>=H[tata]) break;
         aux=poz[H[fiu]]; poz[H[fiu]]=poz[H[tata]]; poz[H[tata]]=aux;
         aux=H[fiu]; H[fiu]=H[tata]; H[tata]=aux;
         fiu=tata;
         tata=fiu/2;
       }
}