#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
/*建图*/
int h[N], ne[N], e[N], money[N],idx;
void connect(int a,int b,int spend)
{
	ne[idx] = h[a];
	e[idx] = b;
	money[idx] = spend;
	h[a] = idx++;
}
/*dijkstra用到的优先队列										*/
/*vector<int> a  = {dis,root} a[0]表示距离 root表示当前结点*/
bool used[N];  /*结点是否到过，注意这里的节点是分层的*/
int spend[N];  /*每个点到初始点的花费*/
bool cmp(vector<int>& a, vector<int>& b)
{
	return a[0] > b[0];
}
priority_queue<vector<int>, vector<vector<int>>, decltype(&cmp)> q(cmp); /*小堆优先队列*/


int main()
{
	memset(h, -1, sizeof h);
	memset(spend, 0x3f, sizeof spend);
	int n, m, k; cin >> n >> m >> k;
	int st, ed; cin >> st >> ed;
	for (int i = 0; i < 6; i++)
	{
		int a, b, s; cin >> a >> b >> s;
		for (int j = 0; j <= k; j++)
		{
			connect(a + j * n, b + j * n, s); /*构建相同层之间的图*/
			connect(b + j * n, a + j * n, s); /*构建相同层之间的图*/
			if (j != k)						  /*构建不同层之间的免费路*/
			{
				connect(a + j * n, b + (j+1) * n, 0); /*构建相同层之间的图*/
				connect(b + j * n, a + (j+1) * n, 0); /*构建相同层之间的图*/
			}
		}
	}
	q.push({0,st});
	spend[st] = 0;
	while (!q.empty())
	{
		auto t = q.top();
		q.pop();
		int temp_dis = t[0], temp_now = t[1]; /*当前距离和结点*/
		if (temp_now % n == ed || used[temp_now])    /*达到终点就可以退了*/
			continue;
		used[temp_now] = true;
 		for (int i = h[temp_now]; i != -1; i = ne[i])
		{
			int next = e[i], sp = money[i];
			if (money[i] + temp_dis < spend[next])
			{
				spend[next] = money[i] + temp_dis;
				q.push({ spend[next],next });
			}
		}
	}
	int res = 0x3f3f3f3f;
	for (int i = 0; i <= k; i++)
	{
		res = min(res, spend[ed + i * n]);
	}
	cout << res << endl;
	return 0;
}