#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 210;

int g[N][N];
int st[N], dist[N], hp[N], cnt[N]; // cnt为经过的城市数量 num为路线方案的数量
int n, k;
int happy[N], path[N], num[N];
string start;
unordered_map<string, int> cti;
unordered_map<int, string> itc;

void dij(int u)
{
    memset(dist, 0x3f, sizeof dist);
    dist[u] = 0;
    cnt[u] = 1;
    num[u] = 1;

    for(int i = 0; i < n; i ++ )
    {
        int t = -1;
        for(int j = 0; j < n; j ++ )
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        st[t] = true;
        for(int j = 0; j < n; j ++ )
        {
            int w = g[t][j];
            if(dist[j] > dist[t] + w)   // 最少耗费优先
            {
                dist[j] = dist[t] + w; // 花费
                path[j] = t;            // 路线
                cnt[j] = cnt[t] + 1;    // 经过城市的数量
                hp[j] = hp[t] + happy[j]; // 幸福感
                num[j] = num[t];          // 方案数
            }
            else if(dist[j] == dist[t] + w) // 耗费相等
            {
                num[j] += num[t];           // 方案数已不唯一
                if(hp[j] < hp[t] + happy[j]) // 幸福感为第二标尺
                {
                    hp[j] = hp[t] + happy[j];
                    path[j] = t;
                    cnt[j] = cnt[t] + 1;
                } 
                else if(hp[j] == hp[t] + happy[j])
                {
                    if(cnt[j] > cnt[t] + 1)     // 所经过城市数量为第三标尺
                    {
                        cnt[j] = cnt[t] + 1;
                        path[j] = t;
                    }
                }
            }
            else continue;
        }
    }
}

void dfs(int u)  // 求路径方案
{
    if(u == 0)
    {
        cout << itc[u] << "->";
        return;
    }
    dfs(path[u]);
    if(itc[u] != "ROM") cout << itc[u] << "->";
    else cout << itc[u];
}

int main()
{
    cin >> n >> k >> start;
    memset(g, 0x3f, sizeof g);
    // 城市与id建立映射
    cti[start] = 0;
    itc[0] = start;

    for(int i = 1, w; i <= n - 1; i ++ )
    {
        string city;
        cin >> city >> w;
        cti[city] = i;
        itc[i] = city;
        happy[i] = w;
    }
    for(int i = 0, c; i < k; i ++ )
    {
        string a, b;
        cin >> a >> b >> c;
        g[cti[a]][cti[b]] = g[cti[b]][cti[a]] = c;
    }
    dij(0);
    int ed = cti["ROM"];

    printf("%d %d %d %d\n", num[ed], dist[ed], hp[ed], hp[ed] / (cnt[ed] - 1));
    dfs(cti["ROM"]);
    return 0;
}