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

using namespace std;

const int N=210;

int n,m;
int d[N][N],w[N];//点权（幸福指数） 
int cnt[N],cost[N],sum[N],pre[N];
//最短路条数，最大点权，最小点数，最低路径的前一个点 
int dist[N];//最短路 
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[t]>sum[t]+1)
                     {
                        sum[j]=sum[t]+1;
                        pre[j]=t;
                     }
                }
            }
    }

}
int main()
{
    memset(d,0x3f,sizeof d);

    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;
    }

    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;
}