The solution has been given, but for a better explanation, repeat it here: There are <=m different graphs, sorting the weights from small to large, and adding the edges of equal edge weights to each side.

First, we can find out what is the adjacency matrix of the s[now].c step by using the previous edge set, and ensure that there is no n before.

Now you can continue to go s[now+1].c-s[now].c on the current map and see if you have seen n in the process. Maintain an adjacency matrix G[i] equal to 1+E+E^2+...+E^{2^i}, where addition represents or, multiplication represents the adjacency matrix transition, and E is the current edge set.

The processing method of G[i] can consider G[0]=1+E, G[i]=G[i-1]^2 (i>=1)

If G[i] is present, so that the adjacency matrix (P*G[i]) can go from 1 to n, then we can go from 1 to n from the current graph.

Of course, there is still uncertainty. We need to know the answer accurately. Multiply it. If *G[i] can't make the adjacency matrix go from 1 to n, multiply E^{2^i} because It can be guaranteed that multiplying by 1, E, ..., E^{2^i} can not make the adjacency matrix go from 1 to n, and finally add 1 to it, and the proof must be satisfied.

If it does not exist or exists but the minimum number of steps required >s[now+1].c-s[now].c, then the answer still needs to go up to the next graph to check if there is a better answer.

But if you don't judge whether it exists or not, but you need the minimum number of steps >s[now+1].c-s[now].c, you can still pass this question.

Here is a set of data to help you detect if your code is really correct:

8 8

1 2 0

2 3 0

3 4 0

4 5 0

5 6 0

6 7 0

7 8 0

6 8 5

Right Answer:6

Simple Answer:7

Finally, paste my blog link

Interested friends can find more interesting things in the blog.