//alg lui Dijkstra in O(n^2) 13.11.2011
#include<iostream>
#include<fstream>
using namespace std;
const int inf=1000000000;
const int nmax=500001;

int n,m,viz[nmax],dist[nmax];
struct graf
{
	int nod,cost;
	graf* next;
} *v[nmax];

void add(int x, int y, int c)
{
	graf *temp=new graf;
	temp->nod=y;
	temp->cost=c;
	temp->next=v[x];
	v[x]=temp;
}

void citire()
{
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	int x,y,c;
	for (int i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		add(x,y,c);
	}
	fin.close();
}

void dijkstra()
{
	for (int i=2;i<=n;i++) //toate nodurile au distanta inf
		dist[i]=inf;
	int dist_min,nod_min=0;
	for (int i=1;i<=n;i++) //pt fiecare nod
	{
		int dist_min=inf;
		for (int j=1;j<=n;j++)  //il cautam pe cel nevizitat cu distanta minima (initial acesta e primul pt ca dist=0)
			if (!viz[j] && dist[j]<dist_min)
			{
				dist_min=dist[j];
				nod_min=j;
			}
		viz[nod_min]=1; //il marcam ca vizitat pe cel gasit cu distanta minima
		graf *temp=v[nod_min]; //vom parcurge toti vecinii nodului gasit anterior
		while (temp) //si daca distanta prin cel anterior e mai mica decat
		{		//distanta curenta (memorata in dist[]) o inlocuim
			if (dist[temp->nod] > dist[nod_min]+temp->cost)
				dist[temp->nod]=dist[nod_min]+temp->cost;
			temp=temp->next;
		}
	}
}

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