#include <bits/stdc++.h>
#define NMAX 50005
#define INF 99999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
bool este[NMAX];
int n,m;
int D[NMAX];
///struct cu 2 componente vector

vector < pair <int,int> > G[NMAX];

struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};
priority_queue<int, vector<int>, compara> Coada;
///fct
void citire();
void afisare();
void dijkstra(int nodst);

int main()
{citire();
 dijkstra(1);
 afisare();

    return 0;
}
void citire()
{int i,x,y,c;
 fin>>n>>m;
 for(i=1;i<=m;i++)
    {fin>>x>>y>>c;
    G[x].push_back(make_pair(y,c));
    }
}
void dijkstra(int nodst)
{
  ///initial dist inf
  int i,nodcr,vec,cost;
  for(i=1;i<=n;i++)
        D[i]=INF;
   D[nodst]=0;
   Coada.push(nodst);
   este[nodst]=1;
   while(!Coada.empty()) ///prima data se initializeaza distantele directe
    {
         nodcr=Coada.top();
         Coada.pop();
         este[nodcr]=0;
         for(i=0;i<G[nodcr].size();i++)
            {
              vec=G[nodcr][i].first;
              cost=G[nodcr][i].second;
              if(D[nodcr]+cost<D[vec])
                {
                 D[vec]=  D[nodcr]+cost;
                 if(!este[vec])
                    {
                      Coada.push(vec);
                      este[vec]=1;

                    }
                }
            }
    }
}
void afisare()
{
  int i;
  for(i=2;i<=n;i++)
      if(D[i]!=INF)
        fout<<D[i]<<" ";
      else
        fout<<0<<" ";

}