#include<cstdio>

#include<cstring>

#include<iostream>

#include<map>

#include<queue>

#define ll long long

#define INF 1e18

using namespace std;

const int N = 1e5+10;

const int M = 5e5+10;

int tot,m,n;

struct Edge

{

    int v, cost, next;

}edge[M];

struct qnode

{

    int loc,level;

    ll dis;

    bool operator < (const qnode &t) const {

        return dis > t. dis;

    }

    qnode(int a=0,int b=0,ll c=0){

        loc=a,level=b,dis=c;

    }

}d[N][2];

int head[M];

bool vis[N][2];

void addedge(int u, int v, ll w)

{

    edge[tot]. v = v;

    edge[tot]. cost = w;

    edge[tot]. next = head[u];

    head[u] = tot ++;

}

void dijkstra(int st)

{

    memset(vis, 0, sizeof(vis));

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

        for(int j=0;j<=1;j++){

            d[i][j].dis=INF;

        }

    }

    d[st][0].dis = 0;

    priority_queue <qnode> q;

    q. push(qnode(st,0,0));

    while(! q. empty()){

        qnode t = q. top();

        q. pop();

        int t1=t.loc,t2=t.level;

        if(vis[t1][t2])continue;

        vis[t1][t2]=true;

        for(int i = head[t1]; i != -1; i = edge[i]. next){

            int v = edge[i]. v;

            int cost = edge[i]. cost;

            if( d[v][t2].dis > d[t1][t2].dis + cost){

                d[v][t2].dis = d[t1][t2].dis + cost;

                q. push(qnode(v,t2,d[v][t2].dis));

            }

            if(t2==0&&d[v][t2+1].dis>d[t1][t2].dis+cost/2){        //分别记录每一段是半价的价格

                d[v][t2+1].dis=d[t1][t2].dis+cost/2;

                q.push(qnode(v,t2+1,d[v][t2+1].dis));

            }

        }

    }

}

int main(){

    while(scanf("%d%d", &n, &m)!=EOF){

        string a,b;

        map<string,int> cnt;

        cnt.clear();

        ll c;

        tot = 1;

        int k=1;

        memset(head, -1, sizeof(head));

        while(m --){

            cin>>a>>b>>c;

            if(!cnt[a])cnt[a]=k++;

            if(!cnt[b])cnt[b]=k++;

            addedge(cnt[a], cnt[b], c);

        }

        cin>>a>>b;

        if(!cnt[a])cnt[a]=k++;

        if(!cnt[b])cnt[b]=k++;

        if(m==0) {

            printf("-1\n");

            continue;

        }

        dijkstra(cnt[a]);

        ll ans=min(d[cnt[b]][0].dis,d[cnt[b]][1].dis);

        if(ans==INF) printf("-1\n");

        else printf("%lld\n",ans);

    }

    return 0;

}