#include <vector>
#include <cstdio>
#include <string>
#define N 50003
#define INF 0x3f3f3f3f
#define st(x) 2*(x)
#define dr(x) st(x)+1
#define pr(x) (x)/2
using namespace std;
struct nod{long nod, cost;};
vector<vector<nod> > v;
vector<int> s;
vector<long> heap,cost;//cu noduri
vector<long>ph;//pozitia in heap
FILE *aux;
void adauga(long a,long b,long c)
{nod x={b,c};
 v[a].push_back(x);
}

void relax(long u)
{vector<nod>::iterator p;
 long i,aux;
 for (p=v[u].begin();p!=v[u].end();++p)
 {if(cost[p->nod]>cost[u]+p->cost)
  {cost[p->nod]=cost[u]+p->cost;
   //percolate
   for (i=ph[p->nod];pr(i);i=pr(i))
   {if(cost[heap[i]]<cost[heap[pr(i)]])
    {aux=heap[i];heap[i]=heap[pr(i)];heap[pr(i)]=aux;
     ph[heap[i]]=i;ph[heap[pr(i)]]=pr(i);
    }
   }
  }
 }
}
void scoate_minim()
{long min,i=0,j,aux;
 heap[1]=*(heap.end()-1);
 ph[heap[1]]=1;
 heap.resize(heap.size()-1);
 
 j=1;
 do
 {i=j;
  min=heap[i];
  if(cost[heap[st(i)]]<cost[min])
  {min=heap[st(i)];j=st(i);}
  if(cost[heap[dr(i)]]<cost[min])
  {min=heap[dr(i)];j=dr(i);}
  if(min!=heap[i])
  {aux=heap[i];
   heap[i]=heap[j];
   heap[j]=aux;
   ph[heap[i]]=ph[i];
   ph[heap[j]]=ph[j];
  }                }
 while(heap[i]!=min);
}
void afisare(long i,long min)
{long j;
fprintf(aux,"%ld %ld \nh: ",i,min);
  for (j=1;j<heap.size();j++){fprintf(aux,"%ld ",heap[j]);}
  fprintf(aux,"\n   1 2 3 4 5 6 7");
  fprintf(aux,"\nb: ");
  for (j=1;j<s.size();j++)
  {if(s[j])
   {fprintf(aux,"1 ");
   }
   else
   {fprintf(aux,"0 ");
   }
  }
  fprintf(aux,"\nc: ");
  for (j=1;j<cost.size();j++)
  {fprintf(aux,"%ld ",cost[j]);
  }
  fprintf(aux,"\n\n");

}
int main ()
{FILE *fin=fopen("dijkstra.in","r");
 FILE *fout=fopen ("dijkstra.out","w");
 aux=fopen("debug.txt","w");
 long n,m,a,b,c,i,min,j;

 fscanf(fin,"%ld%ld",&n,&m);
 v.resize(n+1); s.resize(n+1); heap.resize(n); cost.resize(n+1);ph.resize(n+1);

 vector<long>::iterator q;
 for (q=cost.begin();q!=cost.end();++q){*q=INF;}
 for (i=1;i<heap.size();++i){heap[i]=i+1;ph[i+1]=i;}
 for (i=1;i<=m;i++)
 {fscanf(fin,"%ld%ld%ld",&a,&b,&c);
  adauga(a,b,c);
 }
 cost[1]=0;
// s[1]=true;

 relax(1);
 for (i=1;i<n;i++)
 {
  min=heap[1];
  s[heap[1]]=1;
  afisare(i,min);
  scoate_minim();
  relax(min);



 }
  for (i=2;i<=n;i++)
  {fprintf(fout,"%ld",cost[i]);
  }

 
 return 0;
}