#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#define Nmax 50010
#define inf INT_MAX
#define MP make_pair
#define ii pair<int,int>
#define vii vector < ii >
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector < ii > M[Nmax];
priority_queue < ii, vii, greater<ii> > heap;
int n,m,x,y,z,D[Nmax],viz[Nmax];
void dijkstra(int nod,int n)
{for(int i=1;i<=n;i++)
  {viz[i]=0;
  D[i]=inf/2;//resetare
  }
 ii top;
 //D[nod]=0;
 int poz,d; //poz=indice pentru top, d=distanta pentru top
 heap.push(MP(nod,0));
  while(heap.empty()==0)
  {top=heap.top();
    heap.pop();
   poz=top.first;
   d=top.second;
    if(viz[poz])
     continue;
      viz[poz]=1;
     for(int i=0;i<M[poz].size();i++) //parcurg nodurile adiacente cu top
      if(viz[M[poz][i].first]==0&&M[poz][i].second+d<D[M[poz][i].first]) //daca top nu e  vizitat
        //si daca distanta de la nodul curent la top e mai mica decat cea initiala, modific distanta si o pun in heap
       heap.push(MP(M[poz][i].first,(D[M[poz][i].first]=M[poz][i].second+d)));
  }
}
int main()
{f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y>>z;
 M[x].push_back(MP(y,z));
}
 dijkstra(1,n);
   for(int i=2;i<=n;i++)
    if(D[i]!=inf/2)
     g<<D[i]<<' ';
    else
     g<<0<<' ';
    return 0;
}