#include <iostream>
#include <list>
#define NMAX 50005
#define DMAX 0xfffffff
using namespace std;
typedef pair<int,int> pereche;
typedef list<pereche> lista;
void init(int vector[],int valoare),citire(),rezolvare(),afisare();
int N,M,iHeap,heap[NMAX],distanta[NMAX],pozitie[NMAX];
lista G[NMAX];
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
init(distanta,DMAX);
init(pozitie,-1);
citire();
rezolvare();
afisare();
return 0;
}
void afisare()
{
for(int i=2;i<=N;i++)
cout<<(distanta[i]==DMAX?0:distanta[i])<<" ";
}
void Down(int tata)
{
for(int s=tata<<1,d=s+1;s<iHeap;s=tata<<1,d=s+1)
{
if(d<iHeap&&distanta[heap[d]]<distanta[heap[tata]])
swap(pozitie[heap[d]],pozitie[heap[tata]]),
swap(heap[d],heap[tata]),
tata=d;
else if(distanta[heap[s]]<distanta[heap[tata]])
swap(pozitie[heap[s]],pozitie[heap[tata]]),
swap(heap[s],heap[tata]),
tata=s;
else
return;
}
}
int Pop()
{
int nod=heap[0];
heap[0]=heap[--iHeap];
Down(0);
pozitie[nod]=-1;
return nod;
}
void Up(int fiu)
{
for(int tata=fiu>>1;fiu&&distanta[tata]>distanta[fiu];fiu>>=1,tata=fiu>>1)
swap(pozitie[heap[fiu]],pozitie[heap[tata]]),
swap(heap[fiu],heap[tata]);
}
void Push(int nod,int dist)
{
distanta[nod]=dist;
if(pozitie[nod]==-1)
pozitie[nod]=iHeap,
heap[iHeap++]=nod;
Up(pozitie[nod]);
}
void rezolvare()
{
Push(1,0);
while(iHeap)
{
int nod=Pop();
for(lista::iterator it=G[nod].begin();it!=G[nod].end();it++)
if(distanta[(*it).first]>distanta[nod]+(*it).second)
distanta[(*it).first]=distanta[nod]+(*it).second,
Push((*it).first,distanta[(*it).first]);
}
}
void citire()
{
int s,d,c;
scanf("%d %d",&N,&M);
for(int i=0;i<M;i++)
{
scanf("%d %d %d",&s,&d,&c);
G[s].push_back(pereche(d,c));
}
}
void init(int vector[],int valoare)
{
for(int i=0;i<NMAX;i++)
vector[i]=valoare;
}