#include<fstream>
#include<vector>
#include<queue>
#include<iomanip>
#include<cmath>
using namespace std;

ifstream cin("dmin.in");
ofstream cout("dmin.out");

const int NMAX = 1501;
const int MOD =  104659;
const double EPS = 1e-12;

vector<pair<int,int>> vecini[NMAX];
vector<pair<double,int>> dp;

struct element
{
    int nod;
    bool operator <(const element &lhs) const
    {
        return (dp[lhs.nod].first - dp[nod].first) > EPS;
    }
};

int main()
{
    int n,m,a,b,c; cin >> n >> m;
    for(int i = 1; i <= m ; i++)
        {
            cin >> a >> b >> c; double g = log2(c);
            vecini[a].push_back({b,g});
            vecini[b].push_back({a,g});
        }

    pair<double,int> init = {1 << 30,0};
    dp.resize(n + 1,init);
    dp[1] = {0,1}; priority_queue<element> pq; pq.push({1});
    while(!pq.empty())
        {
            auto v = pq.top() ; pq.pop();
            int nod = v.nod;
            for(auto it : vecini[nod])
                {
                    if(dp[it.first].first > dp[nod].first + it.second)
                        {
                            dp[it.first].first = dp[nod].first + it.second;
                            dp[it.first].second = dp[nod].second; pq.push({it.first});
                        }

                    else if(dp[it.first].first == dp[nod].first + it.second)
                        {
                            ///nu a fost inca scos din pq,urmeaza
                            dp[it.first].second += dp[nod].second;
                            dp[it.first].second %= MOD;
                        }
                }
        }

    for(int i = 2; i <= n ; i++) cout << dp[i].second << " ";

    return 0;

}