#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <map>

using namespace std;

map<string, int> pos;

struct Edge {

    int v, c, next;

} edge[];

int head[], cnt;

int vis[], amm[], aim[],sum[];

int cs, n, m, ans;

string s, t;

void addedge (int u, int v, int c) {

    edge[++cnt].v = v, edge[cnt].c = c;

    edge[cnt].next = head[u];

    head[u] = cnt;

}

void dfs (int x, int s, int k) {

    if(k>=ans) return;

    if (aim[x]) {

        ans = min (ans, k);

        return ;

    }

    if (!vis[x]) s += amm[x], vis[x] = ;

    if(vis[x]&&sum[x]>=s) return;

    sum[x]=max(sum[x],s);

    for (int i = head[x]; i; i = edge[i].next) {

        int v = edge[i].v, c = edge[i].c;

        if (s >= c)  dfs (v, s - c, k + c);

    }

    vis[x] = ;

}

int main() {

    scanf ("%d", &cs);

    while (cs--) {

        pos.clear();

        memset (head, , sizeof head);

        memset(sum,,sizeof sum);

        memset(vis,,sizeof vis);

        cnt = , ans = 0x7fffffff;

        scanf ("%d %d", &n, &m);

        for (int i = ; i <= n; i++) {

            cin >> s;

            pos[s] = i;

            cin >> amm[i] >> s;

            if (s[] == 'y') aim[i] = ;

            else aim[i] = ;

        }

        for (int i = , x; i <= m; i++) {

            cin >> s >> t >> x;

            int u = pos[s], v = pos[t];

            addedge (u, v, x);

            addedge (v, u, x);

        }

        dfs (, , );

        if (ans != 0x7fffffff) printf ("%d\n", ans);

        else puts ("No safe path");

    }

}