#include <stdio.h>
#include <math.h>

#define NMAX 1503
#define INF 2000000000
#define MOD 104659
#define eps 0.0000000001

double a[NMAX][NMAX];
int uz[NMAX];
int n, m;
double dist[NMAX];
int nr[NMAX];

void read()
{
	int i, j;
	int x, y, z;
	scanf("%d %d", &n, &m);

	for(i = 1; i <= n; ++i)
	{
		dist[i] = INF;
		for(j = 1; j <= n; ++j)
			a[i][j] = a[j][i] = INF;
	}

	for(i = 0; i < m; ++i)
	{
		scanf("%d %d %d", &x, &y, &z);

		a[x][y] = a[y][x] = log(z);

		if(x == 1 || y == 1)
			dist[ x != 1 ? x : y ] = a[x][y];
	}
}

void dijkstra()
{
	int i, j, pozmin;
	double min;

	++uz[1];

	for(i = 0; i < n-1; ++i)
	{
		for(min = INF, j = 2; j <= n; ++j)
		{
			if(!uz[j] && dist[j] < min)
			{
				min = dist[j];
				pozmin = j;
			}
		}
        int distj, a1pozmin, apozminj;
		for(++uz[pozmin], j = 2; j <= n; ++j)
		{
			if(!uz[j] && a[pozmin][j] != INF && j != pozmin)
			{

                distj = floor(dist[j]* 1000000);
                a1pozmin = floor(a[1][pozmin] * 1000000);
                apozminj = floor(a[pozmin][j] * 1000000);

                if(distj > a1pozmin + apozminj)
					nr[j] = 1, dist[j] = a[1][pozmin] + a[pozmin][j];

				else if(distj == a1pozmin + apozminj)
					++nr[j], nr[j] %= MOD;


				/*(if(dist[j] > a[1][pozmin] + a[pozmin][j])
					nr[j] = 1, dist[j] = a[1][pozmin] + a[pozmin][j];

				else if(dist[j] - a[1][pozmin] - a[pozmin][j] < eps)
					++nr[j], nr[j] %= MOD;

              */
			}
		}
	}
}

int main()
{
	freopen("dmin.in", "r", stdin);
	freopen("dmin.out", "w", stdout);

	read();

	dijkstra();

	int i;
	for(i = 2; i <= n; ++i)
	{
		printf("%d ", nr[i]);
	}
	printf("\n");

	fclose(stdin);
	fclose(stdout);

	return 0;
}