Cod sursa(job #277607)
#include <cstdio>
#include <fstream>
#include <queue>
#include <cmath>
#define inff 0x3f3f3f
#define MAX_N 50001
using namespace std;
struct nod
{
long cost;
long n;
};
vector <nod> V[MAX_N];
queue <long long> Q;
char viz[MAX_N];
long long N,M,cati[MAX_N];
long D[MAX_N];
void citire()
{
long long x,y,z;
scanf("%lld %lld",&N,&M);
for(long long i = 1; i <= M; ++i)
{
scanf("%lld %lld %lld",&x,&y,&z);
nod t;
t.n = y;
t.cost = log(z);
V[x].push_back(t);
}
}
void solve()
{
for (int i=0;i<=N;i++)
D[i]=100000000;
Q.push(1);
D[1] = 0;
cati[1]=1;
viz[1] ='1';
while(!Q.empty())
{
long long nod = Q.front();
Q.pop();
viz[nod]='0';
for(typeof V[nod].begin() p = V[nod].begin(); p < V[nod].end(); p++)
if(D[p->n]>D[nod]+p->cost)
{
cati[p->n]=cati[nod];
D[p->n]=D[nod]+p->cost;
if(viz[p->n]!='1')
{
Q.push(p->n);
viz[p->n]='1';
}
}
else
if (D[p->n]==D[nod]+p->cost)
cati[p->n]+=cati[nod];
}
}
void afisare()
{
for(long long i = 2; i <= N; ++i)
printf("%lld ",cati[i]%104659);
printf("\n");
}
int main()
{
freopen ("dmin.in","r",stdin);
freopen ("dmin.out","w",stdout);
citire();
solve();
afisare();
return 0;
}