//pairs of成对  recommanded推荐

// the total number of routes between pairs of cities;
//城市对之间的路线总数；

//the number of different routes with the least cost, 
//the cost, the happiness, and the average happiness (take the integer part only) of the recommanded route.
//推荐路线中成本最低的不同路线的数量、成本、幸福感和平均幸福感（仅取整数部分）。

//If such a route is not unique, the one with the maximum happiness will be recommanded.
//If such a route is still not unique, then we output the one with the maximum average happiness 
//我们应该找到成本最低的路线。
//如果这样的路线不是唯一的，那么选取使人们获得最大幸福感的路线。
//如果这样的路线仍然不是唯一的，那么我们选择平均幸福感最大的路线，数据保证这种路线唯一。
//平均幸福感 = 总幸福感 / 经过的城市数量（初始城市不算）
//找平均幸福感最大，即城市点数最少
//还要输出路径，存一下每个点的前驱是什么

//找最短路，最短路不唯一找点权最大，有相同点权最大，找点数最少的路径
//用dijstra要维护最短路数量

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

using namespace std;

const int N = 210;

int n,m;
int d[N][N];
int dist[N],cnt[N],cost[N];//dist最短距离，cnt最短路数量，cost点权（求最大）
int w[N],sum[N],pre[N];//w每点权值，sum点数（求最少）pre[j] = a,j前一个点是a，记录最短路径的前一个点
bool st[N];

string city[N];
unordered_map<string,int> mp;

void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0,cnt[1] = 1;

    for(int i = 0; i<n; i++)
    {
        int t = -1;
        for(int j = 1; j<=n; j++)
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t = j;
        st[t] = true;
        for(int j = 1; j<=n; j++)
            if(dist[j] > dist[t] + d[t][j])
            {
                dist[j] = dist[t] + d[t][j];
                cnt[j] = cnt[t];
                cost[j] = cost[t] +w[j];
                sum[j] = sum[t] + 1;
                pre[j] = t;
            }
            else if(dist[j] == dist[t] + d[t][j])
            {
                cnt[j] += cnt[t];
                if(cost[j] < cost[t] + w[j])
                {
                    cost[j] = cost[t] + w[j];
                    sum[j] = sum[t] + 1;
                    pre[j] = t;
                }
                else if(cost[j] == cost[t] +w[j])
                {
                    if(sum[j]>sum[t]+1)
                    {
                        sum[j] = sum[t] + 1;
                        pre[j] = t;
                    }
                }
            }
    }
}

int main()
{
    cin>>n>>m>>city[1];
    mp[city[1]] =  1;

    for(int i = 2; i<=n; i++)
    {
        cin>>city[i]>>w[i];
        mp[city[i]] = i;
    }

    memset(d,0x3f,sizeof d);

    while(m--)
    {
        string x,y;
        int c;
        cin>>x>>y>>c;

        int a = mp[x],b = mp[y];
        d[a][b] = d[b][a] = min(d[a][b],c);
    }
    dijkstra();

    int T = mp["ROM"];
    cout<<cnt[T]<<' '<<dist[T]<<' '<<cost[T]<<' '<<cost[T]/sum[T]<<endl;

    vector<int> path;
    for(int i = T; i!=1; i = pre[i]) path.push_back(i);

    cout<<city[1];
    for(int i = path.size()-1; i>=0; i--)
        cout<<"->"<<city[path[i]];
    cout<<endl;
    return 0;
}