#include<cstdio>
#include<vector>

#define inf 1<<30

using namespace std;

int n, m;

vector <int>L[50001];
vector <int>dmin;
vector <bool>viz;

void Dijkstra(int start)
{
	int i, minim, poz = 0;
	
	dmin.push_back(0);
	viz.push_back(false);
	for(i = 1; i <= n; i++)
	{
		dmin.push_back(inf);
		viz.push_back(false);
	}
	
	dmin[start] = 0;
	for(i = 1; i < n; i++)
	{
		minim = inf;
		for(int j = 1; j <= n; j++)
		{
			if(dmin[j] < minim && !viz[j])
			{
				minim = dmin[j];
				poz = j;
			}
		}
		
		if(minim == inf) return;
		
		for(unsigned int j = 0; j < L[poz].size(); j++)
		{
			int ad = L[poz][j] / 10000;
			int c = L[poz][j] % 10000;
			int x = c + dmin[poz];
			
			if(x < dmin[ad] && c != inf) dmin[ad] = x;
		}
		
		viz[poz] = true;
	}
}

int main()
{
	int i, x, y, c;
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &x, &y, &c);
		L[x].push_back(y * 10000 + c);
	}
	
	Dijkstra(1);
	for(i = 2; i <= n; i++) printf("%d ", dmin[i] != inf ? dmin[i] : 0);
	
	return 0;
}