#include<fstream.h>
#include<conio.h>
#include<iostream.h>
#include<limits.h>
#define INF LONG_MAX

long n,m,d[50000],viz[50000],tata[50000],min, p_min;

struct nod{ long v, cost; nod* urm;};
nod *p[50000], *u[50000];

int main()
{
long x,y,c,i,j,x0;
ifstream fin("dijkstra.in");
fin>>n>>m;
for(i=1;i<=m;i++)
{
    fin>>x>>y>>c;
    nod* q;
    q=new nod;
    q->v=y;
    q->cost=c;
    q->urm=NULL;
    
    if(!p[x]) p[x]=u[x]=q;
    else { u[x]->urm=q; u[x]=q; }
    
}
fin.close();

for(i=1;i<=n;i++) d[i]=INF;
x0=1;
nod *q;
q=p[x0];
viz[x0]=1;
while(q)
{
   d[q->v]=q->cost;
   q=q->urm;
}

for(j=1;j<n;j++)
{
min=INF;
  for(i=1;i<=n;i++)
     if(min>d[i] && !viz[i]){ min=d[i]; p_min=i;}
nod *q;
q=p[p_min];      
viz[p_min]=1;
  while(q)
  {   
    if(d[q->v] > d[p_min]+q->cost && !viz[i])
    {
        d[q->v]=d[p_min]+q->cost;
        tata[q->v]=p_min;
    }
    q=q->urm;
   }
}
ofstream fout("dijkstra.out");
for(i=2;i<=n;i++) fout<<d[i]<<" ";
fout.close();
return 0;        
}