For problem statement at 0-999/400-499/460-469/464/problemE.txt this is a correct solution, but verifier at 0-999/400-499/460-469/464/verifierE.go ends with case 21: path is not shortest
exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

const M = 131071
const mod1 = 1000000007
const mod2 = 1000000009
const base2 = 13331

var pow1 [M + 2]int32
var pow2 [M + 2]int32

func init() {
	pow1[0] = 1
	pow2[0] = 1
	for i := 1; i <= M; i++ {
		pow1[i] = int32((int64(pow1[i-1]) * 2) % mod1)
		pow2[i] = int32((int64(pow2[i-1]) * base2) % mod2)
	}
}

type Node struct {
	lc, rc       int32
	hash1, hash2 int32
	sum          int32
}

var nodes = make([]Node, 1, 6000000)

func pushUp(id int32, leftLen int) {
	lc := nodes[id].lc
	rc := nodes[id].rc
	nodes[id].sum = nodes[lc].sum + nodes[rc].sum
	nodes[id].hash1 = int32((int64(nodes[lc].hash1) + int64(nodes[rc].hash1)*int64(pow1[leftLen])) % mod1)
	nodes[id].hash2 = int32((int64(nodes[lc].hash2) + int64(nodes[rc].hash2)*int64(pow2[leftLen])) % mod2)
}

func findFirstZero(rt int32, l, r, x int) int {
	if nodes[rt].sum == int32(r-l+1) {
		return -1
	}
	if r < x {
		return -1
	}
	if l == r {
		return l
	}
	mid := (l + r) / 2
	if x <= mid {
		res := findFirstZero(nodes[rt].lc, l, mid, x)
		if res != -1 {
			return res
		}
	}
	return findFirstZero(nodes[rt].rc, mid+1, r, x)
}

func clearRange(rt int32, l, r, ql, qr int) int32 {
	if rt == 0 {
		return 0
	}
	if ql <= l && r <= qr {
		return 0
	}
	mid := (l + r) / 2
	id := int32(len(nodes))
	nodes = append(nodes, nodes[rt])
	if ql <= mid {
		nodes[id].lc = clearRange(nodes[rt].lc, l, mid, ql, qr)
	}
	if qr > mid {
		nodes[id].rc = clearRange(nodes[rt].rc, mid+1, r, ql, qr)
	}
	pushUp(id, mid-l+1)
	return id
}

func setBit(rt int32, l, r, idx int) int32 {
	id := int32(len(nodes))
	if rt != 0 {
		nodes = append(nodes, nodes[rt])
	} else {
		nodes = append(nodes, Node{})
	}
	if l == r {
		nodes[id].sum = 1
		nodes[id].hash1 = 1
		nodes[id].hash2 = 1
		return id
	}
	mid := (l + r) / 2
	if idx <= mid {
		nodes[id].lc = setBit(nodes[rt].lc, l, mid, idx)
	} else {
		nodes[id].rc = setBit(nodes[rt].rc, mid+1, r, idx)
	}
	pushUp(id, mid-l+1)
	return id
}

func cmpRange(u, v int32, l, r int) int {
	if u == v {
		return 0
	}
	if nodes[u].hash1 == nodes[v].hash1 && nodes[u].hash2 == nodes[v].hash2 {
		return 0
	}
	if l == r {
		if nodes[u].sum < nodes[v].sum {
			return -1
		} else if nodes[u].sum > nodes[v].sum {
			return 1
		}
		return 0
	}
	mid := (l + r) / 2
	res := cmpRange(nodes[u].rc, nodes[v].rc, mid+1, r)
	if res != 0 {
		return res
	}
	return cmpRange(nodes[u].lc, nodes[v].lc, l, mid)
}

func add(rt int32, x int) int32 {
	y := findFirstZero(rt, 0, M, x)
	if y > x {
		rt = clearRange(rt, 0, M, x, y-1)
	}
	rt = setBit(rt, 0, M, y)
	return rt
}

type Edge struct {
	to, weight int
}

type Item struct {
	u  int
	rt int32
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return cmpRange(pq[i].rt, pq[j].rt, 0, M) < 0 }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(*Item))
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)

	scanInt := func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}

	n := 0
	for _, b := range scanner.Bytes() {
		n = n*10 + int(b-'0')
	}
	m := scanInt()

	adj := make([][]Edge, n+1)
	for i := 0; i < m; i++ {
		u := scanInt()
		v := scanInt()
		w := scanInt()
		adj[u] = append(adj[u], Edge{to: v, weight: w})
		adj[v] = append(adj[v], Edge{to: u, weight: w})
	}

	s := scanInt()
	t := scanInt()

	dist := make([]int32, n+1)
	for i := range dist {
		dist[i] = -1
	}
	dist[s] = 0

	parent := make([]int, n+1)
	visited := make([]bool, n+1)

	pq := make(PriorityQueue, 0)
	heap.Push(&pq, &Item{u: s, rt: 0})

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		u := item.u

		if visited[u] {
			continue
		}
		visited[u] = true

		if u == t {
			break
		}

		for _, edge := range adj[u] {
			v := edge.to
			if visited[v] {
				continue
			}

			checkpoint := len(nodes)
			nrt := add(item.rt, edge.weight)

			if dist[v] == -1 || cmpRange(nrt, dist[v], 0, M) < 0 {
				dist[v] = nrt
				parent[v] = u
				heap.Push(&pq, &Item{u: v, rt: nrt})
			} else {
				nodes = nodes[:checkpoint]
			}
		}
	}

	if dist[t] == -1 {
		fmt.Println("-1")
		return
	}

	fmt.Println(nodes[dist[t]].hash1)

	path := []int{}
	curr := t
	for curr != 0 {
		path = append(path, curr)
		curr = parent[curr]
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	fmt.Println(len(path))
	for i, v := range path {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}