Cod sursa(job #389781)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#define MOD 104659
#define NMAX 1505
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define INF 2000000000
#define eps 1e-10
using namespace std;
int n,m,C[NMAX],var[NMAX];
vector < pair<int,int> >v[NMAX];
long double CF[NMAX],cost[NMAX];
char viz[NMAX];
set <pair <long double,int> > T;
void read()
{
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&C[i]);
v[x].pb(mp(y,i));
v[y].pb(mp(x,i));
}
}
void init()
{
int i;
for (i=2; i<=n; i++)
cost[i]=INF;
}
inline long double modul(long double x)
{
return x<0 ? -x : x;
}
void apel(int nod)
{
int i,y,z;
for (i=0; i<v[nod].size(); i++)
{
y=v[nod][i].f; z=v[nod][i].s;
if (modul(cost[y]+CF[z]-cost[nod])<=eps)
{
if (!viz[y])
apel(y);
var[nod]+=var[y];
if (var[nod]>=MOD)
var[nod]%=MOD;
}
}
viz[nod]=1;
}
void solve()
{
int i,x,y,z;
long double val;
for (i=1; i<=m; i++)
CF[i]=log10(C[i]);
var[1]=1; viz[1]=1;
init();
T.insert(mp(0,1));
while( T.size() > 0 )
{
val = (*T.begin()).first, x = (*T.begin()).second;
T.erase(*T.begin());
for (i=0; i<v[x].size(); i++)
{
y=v[x][i].f; z=v[x][i].s;
if (cost[x]+CF[z]<cost[y])
{
var[y]=0;
cost[y]=cost[x]+CF[z];
T.insert(mp(cost[y],y));
}
}
}
for (i=2; i<=n; i++)
if (!viz[i])
apel(i);
}
void show()
{
int i;
for (i=2; i<=n; i++)
printf("%d ",var[i]);
printf("\n");
}
int main()
{
freopen("dmin.in","r",stdin);
freopen("dmin.out","w",stdout);
read();
solve();
show();
return 0;
}