#include <fstream>
using namespace std;
const int NMAX=50010;
const long MMAX=250010;
const long INF=100000000;
int *a[NMAX], *c[NMAX], n, x[MMAX], y[MMAX], z[MMAX], d[NMAX];;
bool viz[NMAX];
long dist[NMAX];

void dijkstra(int nod);

int main()
{
	long i, m;
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin>>n>>m;
	for (i=0; i<m; i++)
	{
		fin>>x[i]>>y[i]>>z[i];
		d[x[i]]++;
	}//for i
	for (i=1; i<=n; i++)
	{
		a[i]=new int[d[i]+1];
		c[i]=new int[d[i]+1];
		a[i][0]=0;
		c[i][0]=0;
	}//for i
	for (i=0; i<m; i++)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		c[x[i]][++c[x[i]][0]]=z[i];
	}//for i
	dijkstra(1);
	for (i=2; i<=n; i++)
		if (dist[i]==INF)
			fout<<"0 ";
		else
			fout<<dist[i]<<" ";
	return 0;
}//main

void dijkstra(int nod)
{
	bool gasit;
	long min;
	int i;
	for (i=1; i<=n; i++)
		dist[i]=INF;
	dist[nod]=0;
	gasit=1;
	while (gasit)
	{
		for (i=1; i<=a[nod][0]; i++)
		{
		  if ((c[nod][i]>=0)&&((dist[nod]+c[nod][i])<dist[a[nod][i]]))
			  dist[a[nod][i]]=dist[nod]+c[nod][i];
		}//for i
		viz[nod]=1;
		gasit=0;
		min=INF;
		for (i=1; i<=n; i++)
			if ((!viz[i])&&(min>dist[i]))
			{
				min=dist[i];
				gasit=1;
				nod=i;
			}//if
	}//while
}//dijkstra