#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <cfloat>
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
vector <pair <int, long double>> v[1501];
pair <long double, int> d[1501];
struct el
{
long double c;
int nod;
bool operator <(const el &alt) const
{
if (abs(c - alt.c) <= 10*LDBL_EPSILON) //consideram costurile egale
return 0;
return c > alt.c;
}
};
priority_queue <el> p;
bool b[1501];
int main()
{
int n, m, i, j, x, y, z;
long double c;
fin >> n >> m;
for (i = 1; i<=m; i++)
{
fin >> x >> y >> z;
c = log2(z);
v[x].push_back({y, c});
v[y].push_back({x, c});
}
for (i = 1; i<=n; i++)
d[i] = {100000, 0};
d[1] = {0, 1};
p.push({0, 1});
for (i = 1; i<=n; i++)
{
while (p.empty() == 0 && b[p.top().nod])
p.pop();
if (p.empty() == 1)
break;
x = p.top().nod;
p.pop();
b[x] = 1;
for (j = 0; j<v[x].size(); j++)
{
if (abs(d[v[x][j].first].first - (d[x].first + v[x][j].second)) <= 10*LDBL_EPSILON)
{
d[v[x][j].first].second = (d[v[x][j].first].second + d[x].second)%104659;
p.push({d[v[x][j].first].first, v[x][j].first});
}
else if (d[v[x][j].first].first > d[x].first + v[x][j].second)
{
d[v[x][j].first].first = d[x].first + v[x][j].second;
d[v[x][j].first].second = d[x].second;
p.push({d[v[x][j].first].first, v[x][j].first});
}
}
}
for (i = 2; i<=n; i++)
fout << d[i].second << ' ';
return 0;
}