U277825 【MOVE0014】最短路计数

此题为本人搜集，有版权问题，请联系。

给出一个n 个顶点m 条边的无向正权图，顶点编号为1~n。问从顶点1 开始，到 其他每个点的最短路有几条。

第一行两个整数n，m，表示有n 个点，m 条边；\ 下面的m 行每行3 个正整数u, v, w, 表示顶点u, v 之间有一条长度为w 的无向边。

共n 行，每行一个非负整数。第i 行输出从顶点1 到顶点i 有多少条不同的最短路， 由于答案有可能会很大，请对100003 取模后输出。如果无法到达顶点i 则输出0。

$$1