#include <fstream>
#define inf 2000000000

using namespace std;

int heap[50001], dist[50001], poz[50001], n, m;

struct graf
{
	int nod, cost;
	graf* urm;
}* A[50001];

void adauga(int x, int y, int c)
{
	graf* temp = new graf;
	temp->nod = y;
	temp->cost = c;
	temp->urm=A[x];
	A[x]=temp;
}

void citire()
{
	int i, x, y, c;
	ifstream in("dijkstra.in");
	in>>n>>m;
	for(i=1; i<=n; i++)
	{
		heap[i]=poz[i]=i;
		dist[i]=inf;
	}
	dist[1]=0;
	for(i=1; i<=m; i++)
	{
		in>>x>>y>>c;
		adauga(x, y, c);
	}
}

void upheap(int pozitie)
{
	int aux=heap[pozitie];
	while(dist[aux] < dist[heap[pozitie/2]] && pozitie>1)
	{
		heap[pozitie]=heap[pozitie/2];
		poz[heap[pozitie]]=pozitie;
		pozitie=pozitie/2;
	}
	heap[pozitie]=aux;
	poz[heap[pozitie]]=pozitie;
}

void downheap(int pozitie, int N)
{
	int aux, poz_min;
	while(pozitie*2<=N)
	{
		if(pozitie*2==N && dist[heap[pozitie]]>dist[heap[pozitie*2]])
		{
			poz[heap[pozitie]]=pozitie*2;
			poz[heap[pozitie*2]]=pozitie;
			aux=heap[pozitie];
			heap[pozitie]=heap[pozitie*2];
			heap[pozitie*2]=aux;
			return;
		}
		poz_min=(dist[heap[pozitie*2]]<dist[heap[pozitie*2+1]] ? pozitie*2 : pozitie*2+1);
		if(dist[heap[pozitie]]<=dist[heap[poz_min]]) return;
		poz[heap[pozitie]]=poz_min;
		poz[heap[poz_min]]=pozitie;
		aux=heap[pozitie];
		heap[pozitie]=heap[poz_min];
		heap[poz_min]=aux;
		pozitie=poz_min;
	}
}


void dijkstra()
{
	int nod, N=n, i, aux;
	nod=1;
	graf* curent;
	while(N)
	{
		poz[heap[1]]=N;
		poz[heap[N]]=1;
		aux=heap[1];
		heap[1]=heap[N];
		heap[N--]=aux;
		downheap(1, N);
		for(curent=A[nod]; curent!=NULL; curent=curent->urm)
			if(dist[curent->nod]>dist[nod]+curent->cost)
			{
				dist[curent->nod]=dist[nod]+curent->cost;
				upheap(poz[curent->nod]);
			}
		nod=heap[1];
	}
}


int main()
{
	citire();
	dijkstra();
	ofstream out("dijkstra.out");
	for(int i=2; i<=n; i++)
		out<<(dist[i]==inf ? 0 : dist[i])<<' ';
    return 0;
}