#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
const int nmax=1505,inf=104659,mod=104659;
int n,m;
vector <pair<int,int>> muchii[nmax];
bool inCoada[nmax];
int dist[nmax],cnt[nmax],tatic[nmax];
struct cmp
{
bool operator()(int x,int y)
{
return dist[x]>dist[y];
}
};
priority_queue <int,vector<int>,cmp> q;
void dijkstra(int s)
{
while (!q.empty())
{
int nod=q.top();
q.pop();
inCoada[nod]=false;
for (int i=0;i<muchii[nod].size();i++)
{
int vecin=muchii[nod][i].first;
int cost=muchii[nod][i].second;
if ((dist[nod]*cost)%mod==dist[vecin])
{
if (tatic[nod]!=vecin) cnt[vecin]+=cnt[nod];
}
else if ((dist[nod]*cost)%mod<dist[vecin])
{
dist[vecin]=(dist[nod]*cost)%mod;
cnt[vecin]=cnt[nod];
tatic[vecin]=nod;
if (!inCoada[vecin])
{
q.push(vecin);
inCoada[vecin]=true;
}
}
}
}
}
int main()
{
fin >> n >> m;
for (int i=1;i<=m;i++)
{
int x,y,c;
fin >> x >> y >> c;
muchii[x].push_back({y,c});
muchii[y].push_back({x,c});
}
q.push(1);
inCoada[1]=true;
for (int i=1;i<=n;i++)
{
dist[i]=inf;
}
dist[1]=1;
cnt[1]=1;
dijkstra(1);
for (int i=2;i<=n;i++)
fout << cnt[i] << " ";
}