U281953 最短路径

上海交通大学考研机试题（未知年份） 数据范围有所加强

$N$ 个城市，标号从 $0$ 到 $N−1$，$M$ 条道路，第 $K$ 条道路（$K$ 从 $0$ 开始）的长度为 $2^K$，求编号为 $0$ 的城市到其他城市的最短距离

第一行两个正整数 $N,M$，表示有 $N~(2 \le N \le 10000)$ 个城市，$M~(1 \le M \le 50000)$ 条道路 接下来 $M$ 行，每行两个整数，表示相连的两个城市的编号

$N−1$ 行，表示 $0$ 号城市到其他城市的最短路，如果无法到达，输出 $−1$，数值太大的以 $\bmod~100000$ 的结果输出