#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

ifstream fin ("dmin.in");
ofstream fout ("dmin.out");

struct edge_w_cost {int vertex; double cost;};

vector < vector <edge_w_cost> > edge;
vector <int> used, no_paths;
vector <double> dist;
int N, M;

int main()
{
	fin >>N >>M;

	edge.resize(N+1);
	used.resize(N+1);
	dist.resize(N+1);
	no_paths.resize(N+1);

	for (int i = 1; i <= M; ++i)
	{
		int x, y, c;
		fin >>x >>y >>c;
		edge_w_cost temp;
		temp.vertex = y; temp.cost = log(c);
		edge[x].push_back(temp);
		temp.vertex = x;
		edge[y].push_back(temp);
	}

	fill(dist.begin()+2, dist.begin()+N+1, 1<<30);

	queue <int> NodeQ;

	NodeQ.push(1);
	no_paths[1] = 1;

	while (!NodeQ.empty())
	{
        int node = NodeQ.front();
        NodeQ.pop();
        if (used[node])
			continue;
		used[node] = 1;
        for (int i = 0; i < edge[node].size(); ++i)
		{
			int next_node = edge[node][i].vertex;
			double edge_cost = edge[node][i].cost;

            if (fabs(dist[next_node] - dist[node] - edge_cost) < 1e-9)
                no_paths[next_node] = (no_paths[node] + no_paths[next_node]) % 104659;
			else
				if (dist[next_node] > dist[node] + edge_cost)
				{
					NodeQ.push(next_node);
					dist[next_node] = dist[node] + edge_cost;
					no_paths[next_node] = no_paths[node];
				}
		}
	}

	for (int i = 2; i <= N; ++i)
		fout <<no_paths[i] <<' ';
	fout <<'\n';
    return 0;
}