# Geminiで翻訳

import sys
import heapq

def solve():
    # 入力を一括で読み込み (競技プログラミング向けの高速I/O)
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # グラフの構築
    graph = [[] for _ in range(N)]
    idx = 2
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        c = int(input_data[idx+2])
        graph[u].append((v, c))
        idx += 3
        
    S = input_data[idx]
    
    # dist[u][s] は 最大2つの (cost, id) のリストを持つ
    # 異なる頂点で 'C' を2回踏む必要があるため、状態の上位2つを保持する
    dist = [[[] for _ in range(5)] for _ in range(N)]
    
    def update(u, s, c, id_val):
        d = dist[u][s]
        for i, p in enumerate(d):
            if p[1] == id_val:
                if c < p[0]:
                    d[i] = (c, id_val)
                    d.sort()
                    return True
                return False
                
        d.append((c, id_val))
        d.sort()
        if len(d) > 2:
            d.pop()
            
        for p in d:
            if p[1] == id_val:
                return True
        return False

    # 優先度付きキュー (cost, u, state, id)
    pq = []
    update(0, 0, 0, -1)
    heapq.heappush(pq, (0, 0, 0, -1))
    
    while pq:
        cost, u, s, id_val = heapq.heappop(pq)
        
        # 枝刈り (Lazy Deletion)
        valid = False
        for p in dist[u][s]:
            if p[0] == cost and p[1] == id_val:
                valid = True
                break
        if not valid:
            continue
            
        # 隣接頂点への移動
        for v, edge_cost in graph[u]:
            if update(v, s, cost + edge_cost, id_val):
                heapq.heappush(pq, (cost + edge_cost, v, s, id_val))
                
        # 状態の遷移 (K -> C -> P -> C)
        ns = -1
        nid = id_val
        
        if s == 0 and S[u] == 'K':
            ns = 1
        elif s == 1 and S[u] == 'C':
            ns = 2
            nid = u
        elif s == 2 and S[u] == 'P':
            ns = 3
        elif s == 3 and S[u] == 'C' and u != id_val:
            ns = 4
            
        if ns != -1:
            if update(u, ns, cost, nid):
                heapq.heappush(pq, (cost, u, ns, nid))
                
    # 答えの計算 (状態4に到達している頂点の中での最小コストを探す)
    ans = float('inf')
    for i in range(N):
        if dist[i][4]:
            ans = min(ans, dist[i][4][0][0])
            
    print(-1 if ans == float('inf') else ans)

if __name__ == '__main__':
    solve()