#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define MAXN 1550
#define MOD 104659
#define INF 5e100

using namespace std;

int n, m;
int cate[MAXN], used[MAXN];
double best[MAXN];
const double EPS = 1e-9;
struct leg
{
	int y;
	double c;
	leg(int y = 0, double c = 0) : y(y), c(c) { }
	bool operator ()(int a, int b)
	{
		return best[a] > best[b];
	}
};
bool eq(double a, double b)
{
    return (a-b) >= -EPS && (a-b) <= EPS;
}
vector<leg> graf[MAXN];
void citire()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, rc;
		scanf("%d %d %d", &x, &y, &rc);
		double c = log(1.0*rc);
		graf[x].push_back(leg(y, c));
		graf[y].push_back(leg(x, c));
	}
}
priority_queue<int, vector<int>, leg> heap;
void solve()
{
	for (int i = 1; i <= n; i++) best[i] = INF;
	best[1] = 0, cate[1] = 1;
    heap.push(1);
    while (!heap.empty()) {
		int top = heap.top();
		heap.pop();
		if (used[top])
			continue;
		used[top] = 1;
        for (auto v : graf[top]) {
            if (best[top] + v.c < best[v.y]) {
				best[v.y] = best[top] + v.c;
				cate[v.y] = cate[top];
                heap.push(v.y);
            }
            else if (eq(best[top] + v.c, best[v.y]))
				cate[v.y] = (cate[v.y] + cate[top]) % MOD;
        }
    }
}

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

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

	citire();
	solve();
	afisare();

    return 0;
}
//#include <iostream>
//#include <cstdio>
//#include <queue>
//#include <vector>
//#include <cmath>
//
//#define MMAX 2503
//#define NMAX 1503
//#define x first
//#define y second
//#define eps 1e-9
//#define inf 1<<30
//#define mp make_pair
//#define pb push_back
//#define mod 104659
//
//using namespace std;
//int n, m, nr[NMAX];
//double dmin[NMAX];
//vector <pair<double, int> > v[NMAX];
//bool use[NMAX];
//
//class compare
//{
//public:
//    bool operator()(const int &a, const int &b)
//    {
//        if(dmin[a]>dmin[b])
//            return true;
//        return false;
//    }
//};
//
//priority_queue <int, vector<int>, compare> q;
//
//
//void read()
//{
//    freopen("dmin.in", "r", stdin);
//    freopen("dmin.out", "w", stdout);
//    int a, b, c;
//    double cc;
//    scanf("%i %i", &n, &m);
//    for(int i=1; i<=m; i++)
//    {
//        scanf("%i %i %i", &a, &b, &c);
//        cc=log(c);
//        v[a].pb(mp(cc,b));
//        v[b].pb(mp(cc,a));
//    }
//
//}
//
//void dijkstra()
//{
//    for(int i=2; i<=n; i++)
//        dmin[i]=inf;
//
//    q.push(1);
//    nr[1]=1;
//    int x;
//    while(!q.empty())
//    {
//
//        x=q.top();
//        q.pop();
//        if(use[x])
//            continue;
//        use[x]=1;
//        for(int i=0; i<v[x].size(); ++i)
//        {
//            pair<double, int> k=v[x][i];
//
//                if( fabs(dmin[k.y]-dmin[x]-k.x) < eps )
//                {
//                    nr[k.y]+=nr[x];
//                    if(nr[k.y]>mod) nr[k.y]-=mod;
//                }
//                else if(dmin[k.y]>dmin[x]+k.x)
//                {
//                    nr[k.y]=nr[x];
//                    if(nr[k.y]>mod) nr[k.y]-=mod;
//                    dmin[k.y]=dmin[x]+k.x;
//                    q.push(k.y);
//                }
//
//
//        }
//    }
//
//}
//
//int main()
//{
//    read();
//    dijkstra();
//
//    for(int i=2; i<=n; i++)
//        printf("%i ", nr[i]);
//    printf("\n");
//    return 0;
//}