# Arup Guha
# 2/24/2025
# Alternate Solution to 2025 COP 4516 Spring Final Individual Contest Problem:
#                     Follow the Rainbow Brick Roads

# Runs Bellman-Ford on a graph with the edges stored in edges with numV
# vertices starting at vertex s.
def bellmanford(edges, numV, s):

    # Initialize distance array.
    dist = []
    for i in range(numV):
        dist.append(1000000000000)
    dist[s] = 0

    # Do edge relaxation numV times!
    for i in range(numV):
        for e in edges:
            dist[e[1]] = min(dist[e[1]], dist[e[0]] + e[2])

    # Ta da!
    return dist

def main():

    # Store my color map.
    COLORS = "ROYGBIV"
    bitmap = []
    for i in range(256):
        bitmap.append(-1)
    for i in range(len(COLORS)):
        bitmap[ord(COLORS[i])] = i

    nC = int(input())

    # Process cases.
    for loop in range(nC):

        # Get basic input.
        toks = input().split()
        n = int(toks[0])
        m = int(toks[1])
        q = int(toks[2])

        # Set up my seven edge lists.
        edges = []
        for i in range(7):
            edges.append([])

        # Read all edges.
        for i in range(m):
            toks = input().split()
            u = int(toks[0])-1
            v = int(toks[1])-1
            w = int(toks[2])
            c = bitmap[ord(toks[3][0])]

            # Place edge in appropriate color list.
            edges[c].append([u,v,w])
            edges[c].append([v,u,w])

        # Will store all shortest distances here.
        alldist = []

        # Loop through all subset of colors.
        for mask in range(1<<7):

            # This will be the set of edges for the subset mask of colors.
            myg = []
            for j in range(7):

                # Color j is NOT in this subset.
                if (mask&(1<<j)) == 0:
                    continue

                # If we get here, color j is in mask, so add all of its
                # edges.
                for e in edges[j]:
                    myg.append(e)

            # Run Bellman-Ford and add the result to our 2d list.
            alldist.append(bellmanford(myg, n, 0))

        # Handle queries.
        for i in range(q):
            toks = input().split()
            dest = int(toks[0])-1
            mycolors = toks[1]

            # Figure out the mask corresponding to mycolors.
            mymask = 0
            for j in range(len(mycolors)):
                mymask += (1<<bitmap[ord(mycolors[j])])

            # Here's the answer.
            res = alldist[mymask][dest]

            # This is what they want us to print out.
            if res == 1000000000000:
                print(-1)
            else:
                print(res)

# Ta da!
main()