Cod sursa(job #307850)
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
#define MAX_N 1505
#define INF 0x3f3f3f3f
#define MOD 104659
#define eps 1e-9
#define x first
#define d second
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
int N, M;
vector <pair <int, double> > G[MAX_N];
double D[MAX_N];
int T[MAX_N];
void citire()
{
scanf("%d %d",&N, &M);
while(M--)
{
int x, y;
double d;
scanf("%d %d %lf",&x, &y, &d);
double p = log(d);
G[x].push_back(make_pair(y, p));
G[y].push_back(make_pair(x, p));
}
}
void solve()
{
queue <int> Q;
bitset <MAX_N> viz;
for(int i = 1; i < MAX_N; ++i)
D[i] = INF;
D[1] = 0;
T[1] = 1;
Q.push(1);
viz[1] = 1;
for(;!Q.empty(); Q.pop())
{
int nod = Q.front();
viz[nod] = 0;
foreach(G[nod])
{
int act = it -> x;
double dact = it -> d;
if(fabs(D[nod] + dact - D[act]) < eps)
{
T[act] += T[nod];
if(T[act] > MOD)
T[act] -= MOD;
}
if(D[act] - D[nod] - dact > eps)
{
D[act] = D[nod] + dact;
T[act] = T[nod];
if(!viz[act])
{
Q.push(act);
viz[act] = 1;
}
}
}
}
for(int i = 2; i <= N; ++i)
printf("%d ",T[i]);
}
int main()
{
freopen("dmin.in","rt",stdin);
freopen("dmin.out","wt",stdout);
citire();
solve();
}