/*

这题刚开始我以为只要先找到最短路径，然后再把机票最贵的折半就行了，

后来发现，不一定。。。。这样最便宜(。﹏。)

上网搜了一下，有的是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[][];

bool vis[];

struct node

{

    int num,d;

    node(int a,int b){num=a; d=b;}

};

vector<node> s[];

int n,m;

const long long inf=LLONG_MAX;

map<string,int> mp;

void spfa(int k)

{

    for(int i=;i<=n;i++) dis[i][]=dis[i][]=inf,vis[i]=;

    queue<int> Q;

    Q.push(k);

    vis[k]=;

    dis[k][]=dis[k][]=;

    while(!Q.empty())

    {

        int u=Q.front();

        Q.pop();

        vis[u]=;

        for(int i=;i<s[u].size();i++)

        {

            bool flag=;

            if (dis[s[u][i].num][]>dis[u][]+s[u][i].d)

            {

                flag=;

                dis[s[u][i].num][]=dis[u][]+s[u][i].d;

            }

            if (dis[s[u][i].num][]>dis[u][]+s[u][i].d || dis[s[u][i].num][]>dis[u][]+s[u][i].d/)

            {

                dis[s[u][i].num][]=min(dis[u][]+s[u][i].d,dis[u][]+s[u][i].d/);

                flag=;

            }

            if(flag && !vis[s[u][i].num])

            {

                vis[s[u][i].num]=;

                Q.push(s[u][i].num);

            }

        }

    }

    return;

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        int l=,d;

        char ch2[],ch1[];

        for(int i=;i<=n;i++) s[i].clear();

        mp.clear();

        for(int i=;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][]==inf) printf("-1\n");

           else   printf("%lld\n",dis[ecity][]);

    }

    return ;

}

/*

转自：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[*N],vis[*N];

int now,index,k;

__int64 dis[*N];

char name[N][];

map<string,int>M;

struct node{

    int v,w,next;

}edge[*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=;i<*n;i++){

        vis[i]=false;

        head[i]=-;

    }

    now=;

    index=;

}

void dij(int s,int e)

{

    for(int i=;i<=*n;i++){

       dis[i]=inf;vis[i]=false;

    }

    dis[s]=;

    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!=-;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=;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/);

        }

        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 ;

}