{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"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$. \r\n\r\nA palindrome is a string which reads the same forwards and backwards. Note that any string with length $1$ is also a palindrome.\r\n\r\nA walk is a sequence of edges (with repetitions allowed) such that every adjacent pair of edges in the sequence is incident on a common vertex. A walk is called a palindromic walk if the string formed by the concatenation of characters written on the edges of the walk taken in that order, is a palindrome.\r\n\r\nThe cost of a walk is defined as the sum of weights of all the edges in the walk. Note that if an edge appears $p$ times in a walk, its weight has to be added $p$ times to the cost.\r\n\r\nYou have to find the minimum cost of a palindromic walk from $s$ to $t$ or print $-1$ if no palindromic walk exists.\r\n\r\nNote that the graph **might** have multiple edges but won\u0027t have any self loops.\r\n\r\n### Input:\r\n\r\n- First line will contain $T$, the number of testcases. Then the testcases follow. \r\n- The first line of each testcase contains $4$ space separated integers integers: $N, M, s, t$ denoting the number of vertices in the graph, number of edges in the graph, and the end vertices of the walk respectively.\r\n- Each of the next $M$ lines contains the description of an edge. It contains three space separated integers followed by a character: $u, v, w, c$, denoting an undirected edge between vertices $u$ and $v$, having weight $w$ and the character $c$ written on it. \r\n\r\n### Output:\r\nFor each testcase, output in a single line the minimum cost of a palindromic walk from $s$ to $t$, or $-1$ if no such walk exists.\r\n\r\n### Constraints \r\n- $1 \\leq T \\leq 1000$\r\n- $2 \\leq N \\leq 1000$\r\n- $1 \\leq M \\leq 1000$\r\n- Sum of $N$ over all testcases doesn\u0027t exceed $1000$\r\n- Sum of $M$ over all testcases doesn\u0027t exceed $1000$\r\n- $s \\neq t$\r\n- $ 1 \\leq s, t \\leq n$\r\n- Each character $c$ is a lowercase english letter.\r\n- $0 \\leq w \\leq 10^9 $.\r\n- $u \\neq v $\r\n- $ 1 \\leq u, v \\leq n$\r\n\r\n### Sample Input:\r\n```\r\n3\r\n6 6 1 6\r\n1 2 2 a\r\n1 2 3 b\r\n2 3 1 b\r\n3 4 1 a\r\n4 5 1 a\r\n5 6 1 a\r\n3 2 1 3\r\n1 2 1 a\r\n2 3 2 b\r\n3 2 1 2\r\n1 2 1 a\r\n2 3 2 b\r\n```\r\n\r\n### Sample Output:\r\n```\r\n10\r\n-1\r\n1\r\n```\r\n\t\r\n### EXPLANATION:\r\n\r\nIn the first testcase, we choose the walk $1 \\rightarrow 2 \\rightarrow 1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 4 \\rightarrow 5 \\rightarrow 6$ with cost $2 + 2 + 2 + 1 + 1 + 1 + 1 \u003d 10$ . The string formed by concatenation of characters is `aaabaaa`, which is a palindrome . \r\n\r\n**Note** that there are two edges between $1$ and $2$, one having character \u0027a\u0027 written on it and weight $2$ and the other having character \u0027b\u0027 written and weight $3$.\r\n\r\nIn the second testcase, there is no palindromic walk from $1$ to $3$, hence $-1$ has to be printed.\r\n\r\nIn the third testcase we can choose the walk $1 \\rightarrow 2$ having cost $1$ and giving a palindromic string `a`.\r\n"}}]}