"""
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1LL << 60;
using p2 = pair<ll, int>;
template<class T, class U> bool chmin(T& a, U b) { return a > b ? a = b, 1 : 0; }

int main(int argc, char* argv[]) {
    int N, M; cin >> N >> M;
    vector<vector<pair<int, ll>>> G(N), rG(N);
    for(int i = 0; i < M; i++)
    {
        int u, v; ll c;
        cin >> u >> v >> c;
        u--; v--;
        G[u].emplace_back(v, c);
        rG[v].emplace_back(u, c);
    }
    string S; cin >> S;
    vector<ll> d1(N, INF);
    {
        priority_queue<p2, vector<p2>, greater<p2>> pq;
        d1[0] = 0;
        pq.emplace(0, 0);
        while(!pq.empty())
        {
            auto [d, n] = pq.top(); pq.pop();
            if(d1[n] < d) continue;
            for(auto [e, c] : G[n])
            {
                if(chmin(d1[e], d1[n] + c)) pq.emplace(d1[e], e);
            }
        }
    }
    vector<ll> dK(N, INF);
    {
        priority_queue<p2, vector<p2>, greater<p2>> pq;
        for(int i = 0; i < N; i++) if(S[i] == 'K')
        {
            dK[i] = d1[i];
            pq.emplace(d1[i], i);
        }
        while(!pq.empty())
        {
            auto [d, n] = pq.top(); pq.pop();
            if(dK[n] < d) continue;
            for(auto [e, c] : G[n])
            {
                if(chmin(dK[e], dK[n] + c)) pq.emplace(dK[e], e);
            }
        }
    }
    vector<pair<p2, p2>> dP1(N, {p2{INF, -1}, p2{INF, -1}}), dP2(N, {p2{INF, -1}, p2{INF, -1}});
    {
        priority_queue<pair<p2, int>, vector<pair<p2, int>>, greater<pair<p2, int>>> pq;
        for(int i = 0; i < N; i++) if(S[i] == 'C' && dK[i] < INF)
        {
            dP1[i].first = {dK[i], i};
            pq.emplace(p2{dK[i], i}, i);
        }
        while(!pq.empty())
        {
            auto [di, n] = pq.top(); pq.pop();
            auto [d, i] = di;
            if(dP1[n].second.first < d) continue;
            for(auto [e, c] : G[n])
            {
                if(dP1[e].first.first > d + c)
                {
                    if(dP1[e].first.second != i) dP1[e].second = dP1[e].first;
                    dP1[e].first = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
                else if(dP1[e].second.first > d + c && dP1[e].first.second != i)
                {
                    dP1[e].second = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
            }
        }
        for(int i = 0; i < N; i++) if(S[i] == 'C')
        {
            dP2[i].first = {0, i};
            pq.emplace(p2{0, i}, i);
        }
        while(!pq.empty())
        {
            auto [di, n] = pq.top(); pq.pop();
            auto [d, i] = di;
            if(dP2[n].second.first < d) continue;
            for(auto [e, c] : rG[n])
            {
                if(dP2[e].first.first > d + c)
                {
                    if(dP2[e].first.second != i) dP2[e].second = dP2[e].first;
                    dP2[e].first = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
                else if(dP2[e].second.first > d + c && dP2[e].first.second != i)
                {
                    dP2[e].second = {d + c, i};
                    pq.emplace(p2{d + c, i}, e);
                }
            }
        }
    }
    ll ans = INF;
    for(int i = 0; i < N; i++) if(S[i] == 'P')
    {
        auto [pi1, pi2] = dP1[i];
        auto [p1, i1] = pi1;
        auto [p2, i2] = pi2;
        auto [qj1, qj2] = dP2[i];
        auto [q1, j1] = qj1;
        auto [q2, j2] = qj2;
        if(i1 != j1) chmin(ans, p1 + q1);
        if(i1 != j2) chmin(ans, p1 + q2);
        if(i2 != j1) chmin(ans, p2 + q1);
        if(i2 != j2) chmin(ans, p2 + q2);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}
"""

import sys
import heapq

def solve():
    # Fast I/O is critical for translating C++ code without causing TLE in Python
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    G = [[] for _ in range(N)]
    rG = [[] 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])
        G[u].append((v, c))
        rG[v].append((u, c))
        idx += 3
        
    S = input_data[idx]
    
    INF = 1 << 60
    
    # ----------------------------------------------------
    # Dijkstra 1
    # ----------------------------------------------------
    d1 = [INF] * N
    d1[0] = 0
    pq = [(0, 0)]
    
    while pq:
        d, n = heapq.heappop(pq)
        if d1[n] < d:
            continue
        for e, c in G[n]:
            if d1[e] > d1[n] + c:
                d1[e] = d1[n] + c
                heapq.heappush(pq, (d1[e], e))

    # ----------------------------------------------------
    # Dijkstra 2
    # ----------------------------------------------------
    dK = [INF] * N
    pq = []
    for i in range(N):
        if S[i] == 'K':
            dK[i] = d1[i]
            heapq.heappush(pq, (d1[i], i))
            
    while pq:
        d, n = heapq.heappop(pq)
        if dK[n] < d:
            continue
        for e, c in G[n]:
            if dK[e] > dK[n] + c:
                dK[e] = dK[n] + c
                heapq.heappush(pq, (dK[e], e))

    # ----------------------------------------------------
    # Dijkstra 3 (dP1 & dP2)
    # ----------------------------------------------------
    dP1 = [[[INF, -1], [INF, -1]] for _ in range(N)]
    dP2 = [[[INF, -1], [INF, -1]] for _ in range(N)]
    
    pq = []
    for i in range(N):
        if S[i] == 'C' and dK[i] < INF:
            dP1[i][0] = [dK[i], i]
            # Equivalent to pair<p2, int> structure for tie-breaking: (dist, source, node)
            heapq.heappush(pq, (dK[i], i, i)) 
            
    while pq:
        d, i, n = heapq.heappop(pq)
        if dP1[n][1][0] < d:
            continue
        for e, c in G[n]:
            if dP1[e][0][0] > d + c:
                if dP1[e][0][1] != i:
                    dP1[e][1] = list(dP1[e][0])
                dP1[e][0] = [d + c, i]
                heapq.heappush(pq, (d + c, i, e))
            elif dP1[e][1][0] > d + c and dP1[e][0][1] != i:
                dP1[e][1] = [d + c, i]
                heapq.heappush(pq, (d + c, i, e))
                
    pq = []
    for i in range(N):
        if S[i] == 'C':
            dP2[i][0] = [0, i]
            heapq.heappush(pq, (0, i, i))
            
    while pq:
        d, i, n = heapq.heappop(pq)
        if dP2[n][1][0] < d:
            continue
        for e, c in rG[n]:
            if dP2[e][0][0] > d + c:
                if dP2[e][0][1] != i:
                    dP2[e][1] = list(dP2[e][0])
                dP2[e][0] = [d + c, i]
                heapq.heappush(pq, (d + c, i, e))
            elif dP2[e][1][0] > d + c and dP2[e][0][1] != i:
                dP2[e][1] = [d + c, i]
                heapq.heappush(pq, (d + c, i, e))

    # ----------------------------------------------------
    # Calculate Answer
    # ----------------------------------------------------
    ans = INF
    for i in range(N):
        if S[i] == 'P':
            p1, i1 = dP1[i][0]
            p2, i2 = dP1[i][1]
            q1, j1 = dP2[i][0]
            q2, j2 = dP2[i][1]
            
            if i1 != j1: 
                if ans > p1 + q1: ans = p1 + q1
            if i1 != j2: 
                if ans > p1 + q2: ans = p1 + q2
            if i2 != j1: 
                if ans > p2 + q1: ans = p2 + q1
            if i2 != j2: 
                if ans > p2 + q2: ans = p2 + q2
                
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    solve()