#include<bits/stdc++.h>
using namespace std;
const int N=250;
int n,m;
//int start,endd;
int sum,minlen=0x3f3f3f3f,maxsave,allkill;
vector<string> ans;
map<string,int> mp;
int g[N][N];
bool st[N];
struct P{
string id;
int num;
}a[N];
void dfs(string now,string ed,int len,int kill,vector<string> v){
if(len>minlen) return ;
if(now==ed){
if(len<minlen){
ans=v;
minlen=len;
sum=1;
maxsave=v.size();
allkill=kill;
}
else if(len==minlen){
sum++;
if(maxsave<v.size()){
ans=v;
maxsave=ans.size();
allkill=kill;
}
else if(maxsave==v.size()){
if(allkill<kill){
ans=v;
allkill=kill;
}
}
}
}
int t=mp[now];
for(int i=1;i<n;i++){
if(g[t][i]!=-1&&!st[i]){
st[i]=true;
v.push_back(a[i].id);
dfs(a[i].id,ed,len+g[t][i],kill+a[i].num,v);
st[i]=false;
v.pop_back();
}
}
}
int main(){
string sa,ed;
cin>>n>>m>>sa>>ed;
mp[sa]=0;
for(int i=1;i<n;i++){
cin>>a[i].id>>a[i].num;
mp[a[i].id]=i;
}
memset(st,false,sizeof st);
memset(g,-1,sizeof g);
while(m--){
string a,b;int l;
cin>>a>>b>>l;
g[mp[a]][mp[b]]=l;
g[mp[b]][mp[a]]=l;
}
sum=1;
ans.push_back(sa);
vector<string> v;
v.push_back(sa);
st[0]=true;
dfs(sa,ed,0,0,v);
for(int i=0;i<ans.size();i++){
if(i==ans.size()-1) cout<<ans[i]<<endl;
else cout<<ans[i]<<"->";
}
cout<<sum<<" "<<minlen<<" "<<allkill<<endl;
return 0;
}
