I tried to modify my code. But it still returned WA on test #25.

This is the statement and the code: https://codeforces.me/problemset/submission/464/185632015

Thanks a lot!

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, MOD = 1e9 + 7;
int head[N], ed[M], nxt[M], w[M], root[N];
int idx, tot, n, m, _, Start, End;
unsigned long long k[N];

struct SegmentTree
{
	int lc, rc, val;
	unsigned long long h, size;
}tree[N << 7];

struct Heap
{
	int rt, s;
};

int query(int p, int l, int r, int loc)
{
	if (l == r) return p;

	int mid = l + r >> 1;
	if (loc <= mid) return query(tree[p].lc, l, mid, loc);
	else return query(tree[p].rc, mid + 1, r, loc);
}

int cmp(int p, int q, int l, int r)
{
	//cout << l << ' ' << r << ' ' << tree[p].h << ' ' << tree[q].h << ' ' << tree[p].val << ' ' << tree[q].val << endl;
	if (l == r || tree[p].h == tree[q].h) return tree[p].val > tree[q].val;

	int mid = l + r >> 1;
	if (tree[tree[p].rc].h != tree[tree[q].rc].h) return cmp(tree[p].rc, tree[q].rc, mid + 1, r);
	return cmp(tree[p].lc, tree[q].lc, l, mid);
}

bool operator <(const Heap a, const Heap b)
{
	return cmp(root[a.rt], root[b.rt], 1, N - 5);
}

inline void update(int p, int l, int mid)
{
	tree[p].h = tree[tree[p].lc].h * k[mid - l + 1] + tree[tree[p].rc].h;
	tree[p].size = tree[tree[p].lc].size + tree[tree[p].rc].size;
}

inline void add(int a, int b, int c)
{
	ed[idx] = b, w[idx] = c, nxt[idx] = head[a], head[a] = idx ++;
}

int build(int l = 1, int r = N - 5)
{
	int p = ++ tot;//cout << l << ' ' << r << ' ' << p << endl;
	if (l == r) { tree[p].val = tree[p].h = tree[p].size = 0;
	//cout << tree[p].val << endl;
	return p;}

	int mid = l + r >> 1;
	tree[p].lc = build(l, mid);
	tree[p].rc = build(mid + 1, r);

	update(p, l, mid);

	return p;
}

inline int find(int p, int x)
{
    int z = tree[p].rc, lz = (N - 4 >> 1) + 1, rz = N - 5;
    int l = 1, r = N - 5;
    while (l < r)
    {
        int mid = l + r >> 1;
       if (x <= mid)
       {
       	  if (tree[tree[p].rc].size != r - mid) z = tree[p].rc, lz = mid + 1, rz = r;
       	  //cout << lz << ' ' << rz << ' ' << tree[tree[p].rc].size << endl;
       	  r = mid;
       	  p = tree[p].lc;
	   }
	   else l = mid + 1, p = tree[p].rc;
    }
    //cout << lz << ' ' << rz << endl;
    while (lz < rz)
    {
    	//cout << lz << ' ' << rz << endl;
        int mid = lz + rz >> 1;
        if (tree[tree[z].lc].size != mid - lz + 1) z = tree[z].lc, rz = mid;//, cout << 111 << endl;
        else if (tree[tree[z].rc].size != rz - mid) z = tree[z].rc, lz = mid + 1;//, cout << 222 << endl;
        else return rz;
    }
    //puts("");
    return lz - 1;
}

int cover(int now, int q, int l, int r, int ql, int qr)
{
	//cout << l << ' ' << r << ' ' << ql << ' ' << qr << endl;

	int p = 0;
	if (now != root[0]) p = ++ tot;
	else p = root[_];

	tree[p] = tree[q];

	if (ql <= l && r <= qr) { tree[p] = tree[now]; return p;}

	int mid = l + r >> 1;
	if (ql <= mid) tree[p].lc = cover(tree[now].lc, tree[q].lc, l, mid, ql, qr);
	if (qr > mid) tree[p].rc = cover(tree[now].rc, tree[q].rc, mid + 1, r, ql, qr);

	update(p, l, mid);

	return p;
}

int insert(int now, int l, int r, int loc, int x)
{
	int p = ++ tot;//cout << l << ' ' << r << ' ' << p << endl;
	tree[p] = tree[now];
	if (l == r) { tree[p].val = x, tree[p].size = x, tree[p].h = x; return p;}

	int mid = l + r >> 1;
	if (loc <= mid) tree[p].lc = insert(tree[now].lc, l, mid, loc, x);
	else tree[p].rc = insert(tree[now].rc, mid + 1, r, loc, x);

	update(p, l, mid);

	return p;
}

void add(int rt, int x)
{
	int t = query(rt, 1, N - 5, x);
	if (tree[t].val == 0)
	   root[++_] = insert(rt, 1, N - 5, x, 1);
	else
	{
		//cout << 11111111111 << endl;
	    int u = find(rt, x);
	    //cout << u << endl;
	    //for (int j = 1; j <= N - 5; ++j)
			//cout << tree[query(root[rt], 1, N - 5, j)].val << ' ';
		//puts("");
	    root[++_] = insert(rt, 1, N - 5, u + 1, 1);
	    cover(root[0], root[_], 1, N - 5, x, u);
	    //for (int j = 1; j <= N - 5; ++j)
			//cout << tree[query(root[_], 1, N - 5, j)].val << ' ';
		//puts("");
	}
}

inline int read()
{
	register int s = 0, w = 1;
	register char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}

inline int power(int x)
{
	int res = 1, a = 2;
	for (; x; x >>= 1)
	{
		if (x & 1) res = res * a % MOD;
		a = a * a % MOD;
	}
	return res;
}

void dijkstra()
{
	bool v[N];
	int sw[N], st[N], endrt = -1;
	memset(v, 0, sizeof v);
	memset(sw, -1, sizeof sw);
	priority_queue<Heap> heap;
	stack<int> sta;
	heap.push({0, Start});

	while (!heap.empty())
	{
		//for (int i = 1; i <= 4; ++i) cout << v[i] << ' '; puts("");
		Heap t = heap.top();
		heap.pop();
		int u = t.s;

		if (v[u]) continue;
		v[u] = true;
		if (u == End)
		{
			endrt = t.rt;
			break;
		}


		for (int i = head[u]; ~i; i = nxt[i])
		{
			//for (int j = 1; j <= N - 5; ++j)
				//cout << tree[query(root[t.rt], 1, N - 5, j)].val << ' ';
			//puts("");
			//cout << w[i] + 1 << endl;
			//cout << tree[query(root[t.rt], 1, N - 5, w[i] + 1)].val << endl;
			add(root[t.rt], w[i] + 1);
			//for (int j = 1; j <= N - 5; ++j)
				//cout << tree[query(root[_], 1, N - 5, j)].val << ' ';
			//puts("");

			//cout << u << endl;
			//puts("");
			if (!v[ed[i]] && (sw[ed[i]] == -1 || cmp(root[sw[ed[i]]], root[_], 1, N - 5)))
			{
				sw[ed[i]] = _, st[ed[i]] = u;
				heap.push({sw[ed[i]], ed[i]});
			}
			//cout << u << ' ' << sw[u] << ' ' << ed[i] << ' ' << sw[ed[i]] << endl;
			//for (int j = 1; j <= N - 5; ++j)
				//cout << tree[query(root[sw[u]], 1, N - 5, j)].val << endl;
		}
	}

	if (endrt == -1)
	{
		puts("-1");
		return;
	}
	//cout << endrt << endl;
	int ans = 0;
	for (int i = 1; i <= 120 - 5; ++i)
		ans = (ans + (tree[query(root[endrt], 1, N - 5, i)].val ? power(i - 1) : 0)) % MOD;//, cout << i << ' ' << ans << endl;
	//for (int i = 1; i <= N - 5; ++i)
		//cout << tree[query(root[endrt], 1, N - 5, i)].val << endl;
	printf("%lld\n", ans);
	int cnt = 1, tmp = End;
	while (tmp != Start) sta.push(tmp), tmp = st[tmp], ++ cnt;
	printf("%lld\n", cnt);
	printf("%lld ", Start);
	while (!sta.empty())
		  {printf("%lld ", sta.top()); sta.pop();}
}

signed main()
{
	//freopen("data.in", "r", stdin);
	//freopen("data.out", "w", stdout);

	k[0] = 1;
	for (int i = 1; i <= N - 5; ++i)
		k[i] = k[i - 1] * 131;
	memset(head, -1, sizeof head);
	//cout << 11111 << endl;
	n = read(), m = read();
	for (int i = 1; i <= m; ++i)
	{
		int x = read(), y = read(), z = read();
		add(x, y, z); add(y, x, z);
	}
	Start = read(), End = read();
	//cout << Start << ' ' << End << endl;
	//cout << 2222 << endl;
	root[0] = build();
	//cout << 3333 << endl;
	//for (int i = 1; i <= 2; ++i) ++_, root[_] = insert(root[_ - 1], 1, N - 5, i, 1);
	//cout << ((Heap){_, 1} < (Heap){_ - 5, 10}) << endl;
	//add(root[_], 1);
	/*n = read();
	for (int i = 1; i <= n; ++i)
	{
		int x = read();
		++ _;
		root[_] = insert(root[_ - 1], 1, N - 5, i, x);
	}
	int rt1 = _;
	for (int i = 1; i <= n; ++i)
	{
		int x = read();
		++ _;
		root[_] = insert(root[_ - 1], 1, N - 5, i, x);
	}
	int rt2 = _;*/

	//for (int i = 1; i <= 20; ++i) cout << tree[query(root[rt2], 1, N - 5, i)].val << ' ' << tree[query(root[rt2], 1, N - 5, i)].h << endl;
	//cout << tree[root[rt1]].h << ' ' << tree[root[rt2]].h << endl;
	/*if (cmp(root[rt1], root[rt2], 1, N - 5)) printf("a bigger");
	else if (cmp(root[rt2], root[rt1], 1, N - 5)) printf("b bigger");
	else printf("equal");*/

	//for (int i = 1; i <= 10; ++i) cout << tree[query(root[_], 1, N - 5, i)].val << ' ' << query(root[_], 1, N - 5, i) << endl;
	dijkstra();
	//cout << 4444 << endl;
	return 0;
}

This submission returned WA on point #10, but I don't know where is wrong.

Help! Thank u very much.