#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){
  heap[h[n]]=1;
  h[1]=h[n];
  n--;
  cerne (n,1);
}

void dijkstra()
{
  for (int i=2;i<=n;i++)
    drum[i]=inf;
  int val,min=0;
  int numar=1;
  heap[1]=1;
  for (int i=1;i<=n;i++)
  {
    val=inf;
    u=h[1];
    val=drum[u];
/*    for (int j=1;j<=n;j++)
     printf("%d ", drum[j]);
    printf("\n");
    for (int j=1;j<=n;j++)
     printf("%d ", heap[j]);
    printf("\n");
    for (int j=1;j<=n;j++)
     printf("%d ", h[j]);
    printf("\n");
    for (int j=1;j<=n;j++)
     printf("%d ", drum[h[j]]);
    printf("\n**\n");  */
//      if (drum[j] < val && !viz[j])
//        val = drum[j], u=j;
//    viz[u]=1;
    sterge(numar);
    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);
        }
      }
//    if (val=inf) break;

  }
} 


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");
    fclose(stdout);
    return 0;
}