#include<fstream>
#include<set>
#include<vector>
#define Nmax 50007
using namespace std;
vector< pair<int, int> > G[Nmax];
int n, m, i, j, viz[Nmax], nheap, d[Nmax];
struct heap {int ind, cost;};
heap H[Nmax], aux;

void InsertHeap (heap x)
{
	int fiu=nheap+1, tata=(nheap+1)/2;
	while(tata && H[tata].cost>x.cost)
	{
		H[fiu]=H[tata];
		fiu=tata;
		tata/=2;
	}
	H[fiu]=x;
	nheap++;
}
heap ExstractMin()
{
	int tata, fiu;
	heap minim=H[1];
	tata=1;
	fiu=2;
	H[1]=H[nheap];
	 nheap--;
	while(fiu<=nheap)
	{
		if(fiu+1<=nheap && H[fiu+1].cost<H[fiu].cost)
			fiu++;
		if(H[tata].cost>H[fiu].cost)
		{
			aux=H[tata];
			H[tata]=H[fiu];
			H[fiu]=aux;
			tata= fiu; fiu=2*tata;
		}
		else
			break;
	}
	return minim;
}
void dijkstra()
{
	heap aux2;
	for(j=2;j<=n;j++)
	{
		aux=ExstractMin();
		viz[aux.ind]=1;
		for(i=0;i<G[aux.ind].size();i++)
			if(!viz[G[aux.ind][i].first] && d[G[aux.ind][i].first]>aux.cost+G[aux.ind][i].second)
			{
				d[G[aux.ind][i].first]=aux.cost+G[aux.ind][i].second;
				aux2.ind=G[aux.ind][i].first;
				aux2.cost=d[G[aux.ind][i].first];
				InsertHeap(aux2);
			}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i=1;i<=m;i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
	}
	for(i=0;i<G[1].size();i++)
	{
		aux.ind=G[1][i].first;
		aux.cost=G[1][i].second;
		d[G[1][i].first]=aux.cost;
		viz[G[1][i].first]=1;
		InsertHeap(aux);
	}
	for(i=2;i<=n;i++)
		if(!viz[i])
		{
			aux.ind=i;
			aux.cost=Nmax;
			d[i]=Nmax;
			InsertHeap(aux);
		}
		else
			viz[i]=0;
	viz[1]=1;
	dijkstra();
	for(i=2;i<=n;i++)
		if(d[i]==Nmax)
			printf("0 ");
		else
			printf("%d ", d[i]);
	printf("\n");
	
	return 0;
}