/*
这题刚开始我以为只要先找到最短路径，然后再把机票最贵的折半就行了，
后来发现，不一定。。。。这样最便宜(。﹏。)
上网搜了一下，有的是spfa+dp有的分层图，我决定把两种都写一遍(?•??•?)??
*/

/* spfa+dp
 dis[0][i]表示到i点折半的花费 dis[1][i]表示到i点没用过折半的花费
这题还要注意的是花费总额已经超出int范围，要用long long
然而我inf最大值没有改成LLONG_MAX错了好几次
*/

#include <iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
long long dis[100005][2];
bool vis[100005];
struct node
{
    int num,d;
    node(int a,int b){num=a; d=b;}
};
vector<node> s[100005];
int n,m;
const long long inf=LLONG_MAX;
map<string,int> mp;
void spfa(int k)
{
    for(int i=1;i<=n;i++) dis[i][1]=dis[i][0]=inf,vis[i]=0;
    queue<int> Q;
    Q.push(k);
    vis[k]=1;
    dis[k][1]=dis[k][0]=0;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=0;i<s[u].size();i++)
        {
            bool flag=0;
            if (dis[s[u][i].num][1]>dis[u][1]+s[u][i].d)
            {
                flag=1;
                dis[s[u][i].num][1]=dis[u][1]+s[u][i].d;
            }
            if (dis[s[u][i].num][0]>dis[u][0]+s[u][i].d || dis[s[u][i].num][0]>dis[u][1]+s[u][i].d/2)
            {
                dis[s[u][i].num][0]=min(dis[u][0]+s[u][i].d,dis[u][1]+s[u][i].d/2);
                flag=1;
            }
            if(flag && !vis[s[u][i].num])
            {
                vis[s[u][i].num]=1;
                Q.push(s[u][i].num);
            }
        }
    }
    return;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int l=0,d;
        char ch2[15],ch1[15];
        for(int i=1;i<=n;i++) s[i].clear();
        mp.clear();
        for(int i=1;i<=m;i++)
        {
            scanf("%s %s %d",&ch1,&ch2,&d);
            if (!mp[ch1]) mp[ch1]=++l;
            if (!mp[ch2]) mp[ch2]=++l;
            s[mp[ch1]].push_back( node(mp[ch2],d) );
        }
        scanf("%s %s",&ch1,&ch2);
        if (!mp[ch1]) mp[ch1]=++l;//可能m=0，所以有可能开始和结束城市都没有编号
        if (!mp[ch2]) mp[ch2]=++l;
        int scity=mp[ch1];  //开始的城市编号
        int ecity=mp[ch2]; //相要到达的城市编号
        spfa(scity);
        if (dis[ecity][0]==inf) printf("-1\n");
           else   printf("%lld\n",dis[ecity][0]);
    }
    return 0;
}

/*

转自：http://yomean.blog.163.com/blog/static/189420225201110282390985/

一看就想到了分层图，不过如果用分层图，有点杀鸡用牛刀的感觉，因为只有两层。但我还是写了，最后AC了。不过网上很多人都是用建反两向边求解。
而对于分层图求最短路径问题，我们要注意的是，层与层之间的连线都是单向的，而且是从下一层指向上一层，而我们求最短路径的时候，起点总是在下一层，而终点总是在上一层，所以我们可以将经过层与层之间的特殊边的数目控制在n - 1(n是层数）。
 

*/
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<map>
#include<vector>
#define N 100005
#define inf (_I64_MAX)/2
using namespace std;
int n,m;
int head[2*N],vis[2*N];
int now,index,k;
__int64 dis[2*N];
char name[N][10];
map<string,int>M;
struct node{
    int v,w,next;
}edge[15*N];
void addedge(int u,int v,int w)
{
    edge[index].v=v;
    edge[index].w=w; 
    edge[index].next=head[u];
    head[u]=index++;
}    
struct cmp{
    bool operator()(int a,int b){
         return dis[a]>dis[b];
    }
};
priority_queue<int,vector<int>,cmp>Q;
void init()
{
    while(!Q.empty()) Q.pop();
    M.erase(M.begin(),M.end());
    for(int i=0;i<2*n;i++){
        vis[i]=false;
        head[i]=-1;
    }
    now=1;
    index=0;
}
void dij(int s,int e)
{
    for(int i=0;i<=2*n;i++){
       dis[i]=inf;vis[i]=false;
    }
    dis[s]=0;
    vis[s]=true;
    Q.push(s);
    while(!Q.empty()){
        int u=Q.top();
        Q.pop();
        if(u==e){
            printf("%I64d\n",dis[u]);
            return;
        }
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            int w=edge[i].w;
            if(!vis[v] && dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                Q.push(v);
            }
        }
    } 
}
int main(void)
{
    string a,b;
    int x,y,c;
    while(cin>>n>>m)
    {
        init();
        for(int i=0;i<m;i++){
            cin>>a>>b>>c;
            if(M.find(a)==M.end()) M[a]=now++;
            if(M.find(b)==M.end()) M[b]=now++;
            addedge(M[a],M[b],c);
            addedge(M[a]+n,M[b]+n,c);
            addedge(M[a]+n,M[b],c/2);
        }
        cin>>a>>b;
        __int64 ans=inf;
        if(M.find(a)==M.end() || M.find(b)==M.end()){
            puts("-1");continue;
        }
        else dij(M[a]+n,M[b]);
    }
    return 0;
}