#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 1000000002

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
//graful prin liste de adiacenta cu costuri
struct varf {int x, c;};
vector<varf> G[NMAX];
int n, start=1;
int cmin[NMAX];
int pre[NMAX];
bool M[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> H; //max-heap
//in pereche first este costul, second este varful
void citire();
void  inititalizare();
void dijkstra();
void afisare();

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

void citire()
{int i, x, y, cost, m;
 varf vf;
 fin>>n>>m;
 for (i=0; i<m; i++)
     {
      fin>>x>>y>>cost;
      //y intra in lista de adiacenta a lui x
      vf.x=y; vf.c=cost;
      G[x].push_back(vf);
     }
}

void  inititalizare()
{int i;
 pair <int,int> p;
 for (i=1; i<=n; i++) {cmin[i]=INF; pre[i]=start;}
 pre[start]=cmin[start]=0; M[start]=1;
 //parcurg lista de adiacenta a varfului de start si actualizez costurile
 for (i=0; i<G[start].size(); i++)
     {cmin[G[start][i].x]=G[start][i].c;
      p.first= cmin[G[start][i].x];
      p.second=G[start][i].x;
      H.push(p);
     }
}
void dijkstra()
{pair<int,int> p;
 int i, k, vfmin, cost;
 for (k=1; k<n && !H.empty(); )
     {p=H.top(); H.pop();
      vfmin=p.second; cost=p.first;
      if (M[vfmin]==0)
         {
           M[vfmin]=1; k++;
           //optimizez costurile de la vfmin la varfurile adiacente cu el
           for (i=0; i<G[vfmin].size(); i++)
               if (cmin[G[vfmin][i].x]>cost+G[vfmin][i].c)
                  {
                    cmin[G[vfmin][i].x]=cost+G[vfmin][i].c;
                    pre[G[vfmin][i].x]=vfmin;
                    p.first=cmin[G[vfmin][i].x]; p.second=G[vfmin][i].x;
                    H.push(p);
                  }
         }
     }
}
void afisare()
{int i;
 for (i=2; i<=n; i++)
      if (cmin[i]!=INF) fout<<cmin[i]<<' ';
          else fout<<0<<' ';
}