After watching the explanation broadcast, I understood the approach, but it took a while from there. I think this is a problem with relatively heavy implementation.
Consider dividing the answer palindrome LR into string L and string R. Initialize both as empty strings.
When adding $s_i$, add it to the right side of L or to the left side of R.
Suppose after adding $s_i$ several times, we have L="abcde" and R="cba".
At this point, the substring abc already satisfies the palindrome condition, so we can consider it as L="abc" and R="".
Therefore, we can apply Dijkstra’s algorithm with the pair (L, R) as vertices.
Since only prefixes and suffixes of $s_i$ appear as L or R, it’s sufficiently fast with the current constraints.
For transitions from vertex (L, R), check for all $s_i$ whether adding $s_i$ to L or R partially satisfies the palindrome condition. If the condition is satisfied, we can transition to the next vertex.