#include<stdio.h>
#include<malloc.h>
#include<fstream>
using namespace std;

typedef struct _nod
{
	long int info;
	int cost;
	struct _nod *adr;
} nod;

typedef struct
{
	nod *cap;
} list;

list A[100001];
long int C[1000001];
long int viz[100001];
long int Cost[100001];
long int n;
long int m;
long int s;

void citire(void)
{
	long int a;
	long int b;
	int c;
	ifstream fin ("dijkstra.in");
	
	fin >> n >> m;
	for(long int i=1;i<=m;i++)
	{
		fin >> a >> b >> c;
		nod *nou = (nod*)malloc(sizeof(nod));
		nou->info = b;
		nou->cost = c;
		nou->adr = A[a].cap;
		A[a].cap = nou;
	}
}

void parcurgere(void)
{
	C[1] = 1;
	viz[1] = 1;
	long int pi = 1;
	long int pf = 1;
	while(pi<=pf)
	{
//		printf("%d ",C[pi]);
		pi ++;
		nod *q = A[C[pi-1]].cap;
//		viz[C[pi-1]] = 1;
		while(q)
		{
			if(!viz[q->info] || (Cost[C[pi-1]] + q->cost<Cost[q->info]))
			{			
				C[++pf] = q->info;
				if(!Cost[C[pf]])
				  Cost[C[pf]] = Cost[C[pi-1]] + q->cost;
				else if(Cost[C[pi-1]] + q->cost<Cost[C[pf]]);
				{
				  Cost[C[pf]] = Cost[C[pi-1]] + q->cost;
//				  C[++pf] = q->info;
//				  viz[C[pf]] = 0;
				}
				viz[C[pf]] = 1;
			}
			q = q->adr;
		}
	}
}

void afisare(void)
{
	FILE *f = fopen("dijkstra.out","w");
	
	for(long int i=2;i<=n;i++)
		fprintf(f,"%d ",Cost[i]);
	
	fclose(f);
}

int main()
{
	citire();
	parcurgere();
	afisare();
	return 0;
}