#include <fstream>
#include <vector>
#define NMAX 5001
#define inf 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct la
{
	int nod, cost;
};

vector <la> g[NMAX];
//la g[NMAX][NMAX];
bool sel[NMAX];
int cmin[NMAX], pre[NMAX];
int start, n, m;

void citire();
void init();
void rulare();
void afisare();

int main()
{
	citire();
	init();
	rulare();
	afisare();
	return 0;
}

void citire()
{
	int i, a, b, c;
	la nou;
	fin >> n>> m;
	start=1;
	for (i=1; i<=m; i++)
	{
		fin >> a>> b>> c;
		nou.nod=b;
		nou.cost=c;
		g[a].push_back(nou);
		//g[a][0].nod++;
		//g[a][g[a][0].nod].nod=b;
		//g[a][g[a][0].nod].cost=c;
	}
}

void init()
{
	int i;
	for (i=1; i<=n; i++)
	{
		cmin[i]=inf;
		pre[i]=start;
	}
	cmin[start]=0;
	pre[start]=0;
}

void rulare()
{
	int i, cm, nm;
	bool found;
	do
	{
		cm=inf;
		nm=0;
		found=0;
		for (i=1; i<=n; i++)
		{
			if ((cmin[i]<cm)&&(sel[i]!=1))
			{
				cm=cmin[i];
				nm=i;
				found=1;
			}
		}
		sel[nm]=1;
		for (i=0; i<g[nm].size(); i++)
		{
			if (cmin[g[nm][i].nod]>(cmin[nm]+g[nm][i].cost))
			{
				cmin[g[nm][i].nod]=(cmin[nm]+g[nm][i].cost);
				pre[g[nm][i].nod]=nm;
			}
		}
	} while (found);
}

void afisare()
{
	int i, drum[NMAX], ldr, crt;
	for (i=2; i<=n; i++) 
	{
		if (cmin[i]==inf) fout << '0 ';
		else fout << cmin[i]<< ' ';
	}
	/*fout << '\n';
	for (i=1; i<=n; i++)
	{
		if (cmin[i]==inf) fout << "Nu putem ajunge la nodul "<< i<< "!!!\n";
			else
			{
				if (i!=start)
				{
					ldr=0;
					crt=i;
					while (pre[crt]!=0)
					{
						ldr++;
						drum[ldr]=crt;
						crt=pre[crt];
					}
					ldr++;
					drum[ldr]=crt;
					fout << "De la nodul "<< start<< " la nodul "<< i << " avem drumul: ";
					for (crt=ldr; crt>=1; crt--) fout << drum[crt]<< ' ';
					fout << '\n';
				}
			}
	}*/
}