#include <cstdio>
using namespace std;
const int nd=50005,inf=1999999999;
struct nod{ int val; int cost; nod *urm; }*p[nd];
int heap[nd],lgheap,poz[nd],n,m,dist[nd];
void read()
{ int a,b,c,i;
  nod *aux;
freopen("dijkstra.in","r",stdin); scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
    {
    scanf("%d %d %d\n",&a,&b,&c);
    aux=new nod; aux->val=b; aux->cost=c; aux->urm=p[a]; p[a]=aux;
    }
fclose(stdin);
}
void extractmin()
{ int tata,fiu,z;
  bool e;
poz[heap[1]]=-1; poz[heap[lgheap]]=1;
heap[1]=heap[lgheap]; heap[lgheap]=0; --lgheap;
tata=1; fiu=2; e=true;
while(e&&fiu<=lgheap)
    {
    e=false;
    if(dist[heap[fiu+1]]<dist[heap[fiu]]&&fiu+1<=lgheap)++fiu;
    if(dist[heap[tata]]>dist[heap[fiu]])
        {
        e=true;
        z=poz[heap[tata]]; poz[heap[tata]]=poz[heap[fiu]]; poz[heap[fiu]]=z;
        z=heap[tata]; heap[tata]=heap[fiu]; heap[fiu]=z;
        tata=fiu; fiu=tata<<1;
        }
    }
}
void upinheap(int ind)
{ int fiu,tata,z;
  bool e;
fiu=poz[ind];
tata=fiu>>2; e=true;
while(tata>=1&&e)
    {
    e=false;
    if(dist[heap[tata]]>dist[heap[fiu]])
                        {
                        e=true;
                        z=poz[heap[tata]]; poz[heap[tata]]=poz[heap[fiu]]; poz[heap[fiu]]=z;
                        z=heap[tata]; heap[tata]=heap[fiu]; heap[fiu]=z;
                        fiu=tata; tata=fiu>>2;
                        }
    }
}
void solve()
{ int i,x;
  nod *aux;
for(i=1;i<=n;++i)
    {
    dist[i]=inf;
    heap[i]=i;
    poz[i]=i;
    }
dist[1]=0;
lgheap=n;
while(lgheap>=1)
    {
    x=heap[1]; extractmin();
    aux=p[x];
    while(aux!=NULL)
        {
        if(dist[aux->val]>dist[x]+aux->cost){
                                            dist[aux->val]=dist[x]+aux->cost;
                                            upinheap(aux->val);
                                            }
        aux=aux->urm;
        }
    }
}
void write()
{ int i;
freopen("dijkstra.out","w",stdout);
for(i=2;i<=n;++i)
    {
    if(dist[i]==inf)dist[i]=0;
    printf("%d ",dist[i]);
    }
fclose(stdout);
}
int main()
{
read();
solve();
write();
return 0;
}