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

struct date
{
	int c, n;
};

vector <int> muchie[50001], cost[500001];
date coada[500005];
int n, m, a, b, c, in, sf, nod;
char fr[500001];

int cmp (date x, date y)
{
	return x.n < y.n;
}

int main ()
{
	freopen ("dijkstra.in","r",stdin);
	freopen ("dijkstra.out","w",stdout);
	
	scanf ("%d%d", &n, &m);
	for (int i=1; i <= m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		muchie[a].push_back (b);
		cost[a].push_back (c);
	}
	
	coada[0].c = 0;
	coada[0].n = 1; 
	fr[1] = 1;
	for ( ; in <= sf ; in ++)
	{
		nod = coada[in].n;
		for (int i = 0; i < muchie[nod].size (); i++)
			if ( fr[muchie[nod][i]] == 0)
			{
				coada[++sf].c = coada[in].c + cost[nod][i];
				coada[sf].n = muchie[nod][i];
				fr[muchie[nod][i]]=1;
			}
			else
				for (int j=in; j<=sf; j++)
					if( muchie[nod][i] == coada[j].n)
						if (coada[j].c > (coada[in].c + cost[nod][i]))
							coada[j].c = coada[in].c + cost[nod][i];
	}
	sort (coada, coada + sf + 1, cmp);
	for (int i=1; i <= sf; i++)
		printf ("%d ", coada[i].c);
	return 0;
}