#include <bits/stdc++.h>
using namespace std;

template <typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int N, M;
    cin >> N >> M;
    assert(4 <= N && N <= 200'000);
    assert(1 <= M && M <= 300'000);
    vector<vector<pair<int, int>>> E(N);
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        assert(1 <= min(u, v) && max(u, v) <= N);
        assert(1 <= c && c<= 1'000'000'000);
        u--; v--;
        E[u].emplace_back(v, c);
    }
    for (int i = 0; i < N; i++) {
        sort(E[i].begin(), E[i].end());
        for (int j = 0; j + 1 < E[i].size(); j++) {
            assert(E[i][j].first != E[i][j + 1].first);
        }
    }
    string S;
    cin>>S;
    assert(S.size() == N);
    for (auto c : S) assert('A' <= c && c <= 'Z');

    assert(count(S.begin(), S.end(), 'C') <= 5);
    vector<long long> D1(N, 1e18);
    D1[0] = 0;
    min_priority_queue<pair<long long, int>> Q1;
    Q1.emplace(D1[0], 0);
    while (!Q1.empty()) {
        auto [d, v] = Q1.top();
        Q1.pop();
        if (d != D1[v]) continue;
        for (auto [u, c] : E[v]) if (D1[u] > d + c) {
            D1[u] = d + c;
            Q1.emplace(D1[u], u);
        }
    }
    for (int i = 0; i < N; i++) {
        if(S[i] != 'K') D1[i] = 1e18;
        else Q1.emplace(D1[i], i);
    }
    while (!Q1.empty()) {
        auto [d, v] = Q1.top();
        Q1.pop();
        if (d != D1[v]) continue;
        for (auto [u, c] : E[v]) if (D1[u] > d + c) {
            D1[u] = d + c;
            Q1.emplace(D1[u], u);
        }
    }

    vector<pair<long long, int>> D2(N, make_pair(1e18, 1e9));
    vector<pair<long long, int>> D3(N, make_pair(1e18, 1e9));
    min_priority_queue<pair<pair<long long, int>, int>> Q2;
    for (int i = 0; i < N; i++) if (S[i] == 'C') {
        D2[i].first = D1[i];
        D2[i].second = i;
        Q2.emplace(D2[i], i);
    }
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D2[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u] > make_pair(d.first + c, d.second)) {
                D2[u].first = d.first + c;
                D2[u].second = d.second;
                Q2.emplace(D2[u], u);
            }
            if (D2[u].second != d.second) {
                D3[u] =min(D3[u], {d.first + c, d.second});
            }
        }
    }
    for (int i = 0; i < N; i++) Q2.emplace(D3[i], i);
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D3[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u].second != d.second && D3[u] > make_pair(d.first + c, d.second)) {
                D3[u].first = d.first + c;
                D3[u].second = d.second;
                Q2.emplace(D3[u], u);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        if(S[i] != 'P') D2[i] = D3[i] = {1e18, 1e9};
        else Q2.emplace(D2[i], i);
    }
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D2[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u] > make_pair(d.first + c, d.second)) {
                D2[u].first = d.first + c;
                D2[u].second = d.second;
                Q2.emplace(D2[u], u);
            }
            if (D2[u].second != d.second) {
                D3[u] =min(D3[u], {d.first + c, d.second});
            }
        }
    }
    for (int i = 0; i < N; i++) Q2.emplace(D3[i], i);
    while (!Q2.empty()) {
        auto [d, v] = Q2.top();
        Q2.pop();
        if (d != D3[v]) continue;
        for (auto [u, c] : E[v]) {
            if (D2[u].second != d.second && D3[u] > make_pair(d.first + c, d.second)) {
                D3[u].first = d.first + c;
                D3[u].second = d.second;
                Q2.emplace(D3[u], u);
            }
        }
    }
    long long ans = 1e18;
    for (int i = 0; i < N; i++) if (S[i] == 'C'){
        if (D2[i].second != i) ans = min(ans, D2[i].first);
        else ans = min(ans, D3[i].first);
    }
    if (ans > 1e17) ans = -1;
    cout << ans << endl;
    return 0;
}