#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#define NMAX 50002
#define INFINIT 1000000002


using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct varf
       {int x; int c;
        friend bool operator>(varf , varf);
       };

bool operator>(varf a, varf b)
{
    return a.c>b.c;
}

int n, start;
vector<varf> G[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int prec[NMAX];

priority_queue<varf, vector<varf>, greater<varf> > H;

void citire();
void dijkstra();
void afisare();

int main()
{
  citire();
  dijkstra();
  afisare();
  return 0;
}


void citire()
{varf aux;
 int i, a, m;
 fin>>n>>m;
 start=1;
 for (i=0; i<m; i++)
     {
      fin>>a>>aux.x>>aux.c;
      G[a].push_back(aux);
     }
  uz[start]=1;
  for (i=1; i<=n; i++) {cmin[i]=INFINIT; prec[i]=start;}
  cmin[start]=0; prec[start]=0;
  for (i=0; i<G[start].size(); i++)
       {H.push(G[start][i]);
        cmin[G[start][i].x]=G[start][i].c;
       }

}

void dijkstra()
{varf aux, alta;
 int i, nr;
 nr=1;
 while (nr<n && !H.empty())
       {
         aux=H.top(); H.pop();
         if (!uz[aux.x])
            {
              uz[aux.x]=1; nr++;
              for (i=0; i<G[aux.x].size(); i++)
                  if (cmin[aux.x]+G[aux.x][i].c<cmin[G[aux.x][i].x]
                      && !uz[G[aux.x][i].x])
                     {
                       cmin[G[aux.x][i].x]=cmin[aux.x]+G[aux.x][i].c;
                       prec[G[aux.x][i].x]=aux.x;
                       alta.x=G[aux.x][i].x;
                       alta.c=cmin[G[aux.x][i].x];
                       H.push(alta);
                     }
            }

       }
}
void afisare()
{int i;
 for (i=2; i<=n; i++)
      fout<<cmin[i]<<' ';
 fout<<'\n';
 /*for (i=1; i<=n; i++)
     fout<<prec[i]<<' ';
 fout<<'\n';*/
}