#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;
const int maxn=50001;
const int inf=1073741824;
int n, m, s, h[maxn], cost[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]);
      k=fiu;
    }
  } while (fiu);
}
      
void urca(int n, int k){
  int key = drum[h[k]];
  while ((k>1)&&(key<drum[h[tata(k)]])){
    h[k]=h[tata(k)];
    k=tata(k);
  }
  drum[h[k]]=key;
}

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){
  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++)
//      if (drum[j] < val && !viz[j])
//        val = drum[j], u=j;
//    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){
        build(numar);
        drum[it->ind]=it->cost+val;
      }
     
  }
} 


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    for (int i=1;i<=n;i++)
      h[i]=i;
    dijkstra();
    for (int i=2;i<=n;i++)
      printf("%d ", drum[i]<inf ? drum[i] : 0);
    printf("\n");
    return 0;
}