#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-8;
const double INF = 1e9 + 2435986;
vector<pair<int,double>> 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;
}
};
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 = {INF,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) > EPS)
{
dp[it.first].first = dp[nod].first + it.second;
dp[it.first].second = dp[nod].second; pq.push({it.first});
}
else if(abs(dp[it.first].first - dp[nod].first - it.second) <= EPS)
{
///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;
}