Chefir

    #include <iostream>
    #include <vector>
    #include <set>
    #include <climits>
    #include <algorithm>

    #define ULLONG unsigned long long
    constexpr auto INF = ULLONG_MAX;
    typedef std::pair<ULLONG, int> edge;

    std::vector<std::vector<edge>> G;

    template <class type>
    std::ostream& operator<<( std::ostream &Out, const std::vector<type> &Vec )
    {
      for (auto & a : Vec)
        Out << a << " ";
      return Out;
    }

    std::pair<ULLONG, ULLONG> dijkstra( int S, int b, int c )
    {
      const int n = G.size();

      std::vector<ULLONG> d(n, INF);
      std::set<edge> que;

      d[S] = 0;
      que.insert(edge(d[S], S));

      while (!que.empty())
      {
        int v = que.begin()->second;

        que.erase(que.begin());

        // relax
        for (auto & to : G[v])
          if (d[v] + to.first < d[to.second])
            que.erase(edge(d[to.second], to.second)), que.insert(edge((d[to.second] = d[v] + to.first), to.second));
      }

      return std::pair<ULLONG, ULLONG>(d[b], d[c]);
    }

    int main()
    {
      int n, m, a, b, c;
      ULLONG w1, w2, w3;

      scanf("%i%i", &n, &m);

      G.resize(n);

      while (m--)
        scanf("%i%i%llu", &a, &b, &w1), G[--a].push_back(edge(w1, --b)), G[b].push_back(edge(w1, a));

      scanf("%i%i%i", &a, &b, &c);

      a--, b--, c--;

      auto
        res1 = dijkstra(a, b, c),
        res2 = dijkstra(b, a, c);

      w1 = res1.first, w2 = res1.second, w3 = res2.second;

      if (w2 != INF && w1 != INF && w3 != INF)
      {
        ULLONG res = 0;

        if (w1 < w2)
        {
          if (w1 < w3)
            res = w1 + std::min(w2, w3);
          else
            res = w3 + w1;
        }
        else // w2 <= w1
        {
          if (w2 < w3)
            res = w2 + std::min(w3, w1);
          else
            res = w3 + w2;
        }

        printf("%llu", res);
      }
      else
        printf("-1");

      return 0;
    }