#include <fstream.h>

struct NOD
{
	unsigned short nod,cost;
	NOD *next;
} *Graph[50001];

unsigned short N,K=1,Heap[50001],okh[50001];
unsigned int M,Cost[50001],INF=1<<31;
bool ok[50001];

void GetGraph();
void Up(unsigned short key);
void Down(unsigned short key);
void Dijkstra();


int main()
{
	unsigned short i;
	
	GetGraph();
	Dijkstra();
	
	ofstream out("dijkstra.out");
	for(i=2;i<=N;++i)
		if(Cost[i]==INF) out<<"0 ";
		else out<<Cost[i]<<' ';
	out<<'\n';
	out.close();
	
	return 0;
}

void GetGraph()
{
	NOD *p;
	unsigned short i,A,B,C;
	
	ifstream in("dijkstra.in");
	in>>N>>M;
	for(i=1;i<=M;++i)
	{
		in>>A>>B>>C;
		p=new NOD; p->nod=B; p->cost=C; p->next=Graph[A];
		Graph[A]=p;
	}
	in.close();
}

void Up(unsigned short what)
{
	unsigned short key=Heap[what],father=what/2;
	
	while(1<what && Cost[Heap[father]]>Cost[key])
	{
		Heap[what]=Heap[father];
		okh[Heap[father]]=what;
		what=father; father=what/2;
	}
	Heap[what]=key;
	okh[key]=what;
}
	
void Down(int what)
{
	unsigned short key=Heap[what];
	int son,left,right;
	
	do
	{
		son=0; left=what*2;
		if(left<=K)
		{
			son=left; right=left+1;
			if(right<=K && Cost[Heap[right]]<Cost[Heap[left]]) son=right;
			if(Cost[key]<Cost[Heap[son]]) son=0;
		}
		if(son){ Heap[what]=Heap[son]; okh[Heap[son]]=what; what=son; }
	}while(son);
	Heap[what]=key;
	okh[key]=what;
}

void Dijkstra()
{
	NOD *p;
	unsigned int sum;
	unsigned short i;
	
	for(i=2;i<=N;++i) Cost[i]=INF;
	Heap[1]=1;
	
	while(K>0)
	{
		i=Heap[1]; p=Graph[i];
		Heap[1]=Heap[K]; --K; okh[Heap[1]]=1; Down(1);
		while(p)
		{
			sum=Cost[i]+p->cost;
			if(sum<Cost[p->nod])
			{	
				Cost[p->nod]=sum;
				if(!okh[p->nod]){ Heap[++K]=p->nod; okh[p->nod]=K; Up(K); }
				else Up(okh[p->nod]);
			}
			p=p->next;
		}
	}
}