#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;
const int maxn=250001;
const int inf=1073741824;
int n, m, s, h[maxn], cost[maxn],heap[maxn];
struct rec{
  int ind;
  int cost;
}x;
 
deque<int> coada;
vector<rec> vecini[maxn];
int drum[maxn];
int u;
 
inline int tata(int nod){
  return nod>>1;
}
 
inline int fiu_stang(int nod){
  return nod*2;
}
 
inline int fiu_drept(int nod){
  return nod*2+1;
}
 
inline int min() {
  return h[1];
}
void cerne(int n, int k){ 
  int fiu;
  do {
    fiu=0;
    if (fiu_stang(k)<=n){
      fiu = fiu_stang(k);
      if (fiu_drept(k)<=n && drum[h[fiu_drept(k)]]<drum[h[fiu_stang(k)]]){
        fiu=fiu_drept(k);
      }
      if (drum[h[fiu]]>=drum[h[k]])
        fiu=0;
    }
    if (fiu){
      swap(h[k], h[fiu]);
      heap[h[k]]=k;
      heap[h[fiu]]=fiu;
      k=fiu;
    }
  } while (fiu);
}
       
void urca(int n, int k){
  int key = h[k];
  while ((k>1)&&(drum[key]<drum[h[tata(k)]])){
    h[k]=h[tata(k)];
    heap[h[k]]=tata(k);
    k=tata(k);
  }
  h[k]=key;
  heap[h[k]]=k;
}
 
void build(int n){
  for (int i=n/2; i>0; i--){
    cerne(n,i);
  }
}
 
 
void citire()
{
  int a,b,c;
  scanf("%d %d ",&n,&m);
  for (int i=1;i<=m;i++)
  {
    scanf("%d %d %d ", &a, &b, &c);
    x.ind=b;
    x.cost=c;
    vecini[a].push_back(x);
  }
}
 
void sterge(int &n, int k){
  heap[h[k]]=n;
  h[k]=h[n];
  n--;
  if ((k>1)&&(drum[h[k]]<drum[h[tata(k)]])){
    urca(n,k);
  } else {
    cerne (n,k);
  }
}
 
void dijkstra()
{
  for (int i=2;i<=n;i++)
    drum[i]=inf;
  int val,min=0;
  int numar=n;
  for (int i=1;i<=n;i++)
  {
    val=inf;
    u=h[1];
    val=drum[u];
/*    for (int j=1;j<=n;j++)
109.     printf("%d ", drum[j]);
110.    printf("\n");
111.    for (int j=1;j<=n;j++)
112.     printf("%d ", heap[j]);
113.    printf("\n");
114.    for (int j=1;j<=n;j++)
115.     printf("%d ", h[j]);
116.    printf("\n");
117.    for (int j=1;j<=n;j++)
118.     printf("%d ", drum[h[j]]);
119.    printf("\n**\n");  */
120.//      if (drum[j] < val && !viz[j])
121.//        val = drum[j], u=j;
122.//    viz[u]=1;
    sterge(numar,1);
    for (vector<rec>::iterator it=vecini[u].begin();it!=vecini[u].end();it++)
      if (drum[it->ind]>it->cost+val){
        drum[it->ind]=it->cost+val;
        if (heap[it->ind]!=-1){
          urca(numar,heap[it->ind]);
        } else {
          h[++numar]=it->ind;
          heap[it->ind]=numar;
          urca (numar,numar);
        }
      }
      
  }
}
 
 
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    for (int i=1;i<=n;i++){
      h[i]=i;
      heap[i]=-1;
    }
    dijkstra();
    for (int i=2;i<=n;i++)
      printf("%d ", drum[i]<inf ? drum[i] : 0);
    printf("\n");
    return 0;
}