#include <fstream>
#include <queue>
#include <functional>
#include <vector>
#define LMAX 50005
#define INF 999999999

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

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

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

priority_queue < varf, vector<varf>, greater<varf> > H;
vector<varf> G[LMAX];

int n;
bool uz[LMAX];
int cmin[LMAX];
int prec[LMAX];
int start;

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

int main()
{
citire();
dijkstra();
afisare();
fin.close();
fout.close();
return 0;
}


void citire()
    {
     int i;
     int x;
     int m;
     varf aux;
     fin>>n>>m;
     for (i=1;i<=m;i++)
         {
          fin>>x>>aux.x>>aux.cost;
          G[x].push_back(aux);
         }
     start=1;
     uz[start]=1;
     for (i=1;i<=n;i++)
          cmin[i]=INF;
     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].cost;
          prec[G[start][i].x]=start;
         }
    }

void dijkstra()
    {
     int nr=1;
     int i;
     varf aux;
     varf piH;
     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[G[aux.x][i].x] > cmin[aux.x] + G[aux.x][i].cost && !uz[G[aux.x][i].x])
                     {
                      cmin[G[aux.x][i].x]= cmin[aux.x] + G[aux.x][i].cost;
                      prec[G[aux.x][i].x]= aux.x;
                      piH.x=G[aux.x][i].x;
                      piH.cost=cmin[G[aux.x][i].x];
                      H.push(piH);
                     }
             }
         }
    }

void afisare()
    {
     int i;
     for (i=2;i<=n;i++)
         if (cmin[i]==INF)
           fout<<0<<' ';
           else
           fout<<cmin[i]<<' ';
     fout<<'\n';
    }