Palindromic Walks

You are given an undirected graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered from 1 to $N$. Each edge has associated with it, a character (a lowercase english alphabet) and a weight. You are given two **distinct** vertices $s$ and $t$. A palindrome is a string which reads the same forwards and backwards. Note that any string with length $1$ is also a palindrome. A walk is a s