#include <cstdio>
#include <vector>
using namespace std;

const int INF = 2000000000;

const int N = 50001;

vector<int> vecin[N]; int n;
vector<int> cost_catre_vecin[N];

int d[N];
int coada[N];
bool vizitat[N];








#include <sstream>

string show_v(vector<int> x)
{
 stringstream s;
 s<<"[ ";
 for (vector<int>::iterator it = x.begin(); it!=x.end(); it++)
 s<<*it<<' ';
 s<<']';
 return s.str();
}






void citire()
{
	int a,b,c,m;
	scanf("%i%i",&n,&m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%i%i%i",&a,&b,&c);
		vecin[a].push_back(b);
		cost_catre_vecin[a].push_back(c);
	}
}

void dijkstra()
{
	int nevizitate = n;
	int elem_curent,dist_elem_curent;
	for (int i = 2; i <= n; ++i)
		d[i] = INF;
	d[1] = 0;
	while (nevizitate > 0)
	{
		elem_curent = 0;
		dist_elem_curent = INF;
		for (int i = 1; i <= n; ++i)
			if ((!vizitat[i])&&(d[i] < dist_elem_curent))
			{
				dist_elem_curent = d[i];
				elem_curent = i;
			}
		if (dist_elem_curent == INF)
			break;
		for (int i = 0; i < vecin[elem_curent].size(); ++i)
			if (d[elem_curent] + cost_catre_vecin[elem_curent][i] < d[vecin[elem_curent][i]])//cost_catre_vecin[elem_curent][i] -> d[elem_curent][vecin[elem_curent][i]]
			//{	
				d[vecin[elem_curent][i]] = d[elem_curent] + cost_catre_vecin[elem_curent][i];
			    //prec[vecin[elem_curent][i]] = elem_curent;
	        //}
		vizitat[elem_curent] = true; //scos din coada
		--nevizitate;
	}
}

void afisare()
{
	for (int i = 2; i <= n; ++i)
		if (d[i] == INF)
			printf("0 ");
		else
			printf("%i ",d[i]);
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra();
	afisare();
	return 0;
}