这题是真的有趣。虽然场上并没有去写（感觉写了也是不可能过的，因为细节比较多）。
一开始觉得「难道不是把出边 xjb 排个序就做完了嘛」。然后发现被叉了，心情郁闷(x
考虑如何比较「编号相连得到的十进制数」的大小，那必然是先比较位数，再从头开始比较权值。于是就有个特别强的建图技巧：拆边。考虑把一条编号为 $(\overline{a_1a_2\cdots a_k})_{10}$ 的边拆成两条有向链，链上的边的边权分别为 $a_1,a_2\cdots a_k$。
然后考虑进行类似分层图的 BFS。这个分层图的细节很丰富：
0、分层的目的是，控制遍历顺序，使得 BFS 的最优性也在当前问题中体现。即使得对于每个点，最先被遍历时一定是最短路。
1、首先要先忽略边权进行分层。
2、其次考虑如果存在多条出边，必然是走权最小的那条边。
3、只符合上面两条还是不对的。因为考虑如果某个点 $t$ 有两条入边 $e_1,e_2$ 满足 $val(e_1)<val(e_2)$，他们在 BFS 树上的深度相同，那么如果单纯按点来转移，可能会出现先走 $e_2$ 再走 $e_1$ 的情况，而此时 $t$ 已经被更新完毕就会导致出错。所以还要按照边权从 $0$ 到 $9$ 进行再分层。
可以知道这样做最后复杂度一定不会超过 $O(10\times m)$ 。
```[cpp
int ob ;
int cnt ;
int n, m ;
int arr[M] ;
int f[N] ;
int g[N] ;
int T ;
vector <int> q[N] ;
vector <int> E[N][10] ;
int main(){
cin >> n >> m ;
int x, y, z ; cnt = n ;
for (int i = 1 ; i <= m ; ++ i){
x = qr(), y = qr() ; ob = 0 ; z = i ;
while (z) arr[++ ob] = z % 10, z /= 10 ; z = x ;
for (int j = ob ; j > 1 ; -- j)
E[x][arr[j]].push_back(++ cnt), x = cnt ;
E[x][arr[1]].push_back(y) ;
for (int j = ob ; j > 1 ; -- j)
E[y][arr[j]].push_back(++ cnt), y = cnt ;
E[y][arr[1]].push_back(z) ;
}
g[1] = T = 1 ;
q[1].push_back(1) ;
for (int d = 1 ; d <= T ; ++ d){
// if (!q[d].size()) break ;
for (z = 0 ; z < 10 ; ++ z){
auto t = q[d].begin() ;
while (t != q[d].end()){
x = *t ;
for (auto y : E[x][z]){
if (g[y]) continue ;
f[y] = (f[x] * 10ll + z) % P ;
g[y] = 1, q[T + 1].push_back(y) ;
}
++ t ;
}
if (q[T + 1].size()) ++ T ;
}
}
for (int i = 2 ; i <= n ; ++ i)
printf("%d\n", f[i]) ; return 0 ;
}
```
#