#include <fstream.h>

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

struct el
{
	unsigned short nod,cost;
} Heap[50001];

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

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


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

	return 0;
}

void GetGraph()
{
	NOD *p;
	unsigned short A,B,C;
	
	ifstream in("dijkstra.in");
	in>>N>>M;
	for(int 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)
{
	el key=Heap[what];
	unsigned short father=what/2;
	
	while(1<what && Heap[father].cost>Heap[what].cost)
	{
		Heap[what]=Heap[father];
		what=father; father=what/2;
	}
	Heap[what]=key;
}
	
void Down(unsigned short what)
{
	el key=Heap[what];
	int son,left,right;
	
	do
	{
		son=0; left=what*2;
		if(left<=K)
		{
			son=left; right=left+1;
			if(right<=K && Heap[right].cost<Heap[left].cost) son=right;
			if(key.cost<Heap[son].cost) son=0;
		}
		if(son){ Heap[what]=Heap[son]; what=son; }
	}while(son);
	Heap[what]=key;
}

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