C++ :

#include <stdio.h>
#include <string.h>

#include <vector>
#include <queue>

typedef std::pair<int, int> pii;
typedef long long llong;
const int N = 10000 + 5;
const int INF = 0x3f3f3f3f;

std::vector<pii> g[N];
bool vis[N];

void spfa(int s, int d[N])
{
  std::queue <int> q;
  memset(d, 0x3f, sizeof(int) * N);
  memset(vis, 0, sizeof(bool) * N);
  q.push(s); vis[s] = true; d[s] = 0;
  for (; !q.empty(); )
  {
    int u = q.front(); q.pop();  vis[u] = false;
    for (int i = 0; i < g[u].size(); ++i)
    {
      int v = g[u][i].first;
      int c = g[u][i].second;
      if (d[u] + c < d[v])
      {
        d[v] = d[u] + c;
        if (!vis[v])
        {
          vis[v] = true;
          q.push(v);
        }
      }
    }
  }
}

int da[N];
int db[N];
int dc[N];

int main()
{
  int casc;
  scanf("%d", &casc);
  for (int casi = 1; casi <= casc; ++casi) {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
      g[i].clear();
    int a, b, c;
    for (; m--; ) {
      scanf("%d %d %d", &a, &b, &c);
      g[a].push_back(pii(b, c));
      g[b].push_back(pii(a, c));
    }
    scanf("%d %d %d", &a, &b, &c);
    spfa(a, da); spfa(b, db); spfa(c, dc);
    llong result = 0LL + da[b] + db[c] + dc[a];
    for (int i = 1; i <= n; ++i) {
      result = std::min(result, 0LL + da[i] + db[i] + dc[i]);
    }
    if (result >= INF)
      result = -1;
    printf("%d\n", (int) result);
  }
  return 0;
}