#include <iostream>
#include <fstream>
using namespace std;
long long m,n,i,j;
int d[2001];
int C[2001][2001];
int x,y,cost;

void dijkstra(int x)
{
	int i,min,viz[2001],tata[2001];
	int ok,k;
	for (i=1;i<=n;i++)
	{
		d[i]=C[x][i];
		tata[i]=x;
		viz[i]=0;
	}
	tata[x]=0;
	viz[x]=1;
	ok=1;
	while (ok)
	{
		min=10000;
		for (i=1;i<=n;i++)
			if (viz[i]==0 && min>d[i])
			{
				min=d[i];
				k=i;
			}
		if (min!=10000)
		{
			viz[k]=1;
			for (i=1;i<=n;i++)
				if (viz[i]==0 && d[i]>d[k]+C[k][i])
				{
					d[i]=d[k]+C[k][i];
					tata[i]=k;
				}
		}
		else ok=0;
	}
}

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			C[i][j]=10000;
		
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>cost;
		C[i][i]=0;
		C[x][y]=cost;
	}
	dijkstra(1);
	for (i=2;i<=n;i++)
		g<<d[i]<<" ";
	f.close();
	g.close();
	return 0;
}