解题报告：

题目就不描述了。

就是求第一个点到其他点的最短距离和。（单源最短路）

再加上 其他所有点到第一个点的最短距离和。 （把图反向后的单源最短路）

点多，边多，spfa可过。

代码如下：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
#define SIZE 1000001
struct edge{int to, value, next;}y[SIZE];
int t, v, e, x[SIZE], from, to, id, que[SIZE * 2], vst[SIZE];
int sta[SIZE][2], cnt;
long long d[SIZE];
long long spfa()
{
    memset(vst, 0, sizeof(int) * (v + 1));
    memset(d, -1, sizeof(long long ) * (v + 1));d[1] = 0;
    int head = 0, tail = 0;
    que[tail++] = 1;vst[1] = 1;
    while(head != tail)
    {
       
        from = que[head], id = sta[que[head]][0];
        while(id != -1)
        {
            to = y[id].to;
            if (d[to] == -1 || d[from] + y[id].value < d[to])
            {
                d[to] = d[from] + y[id].value;
                if (!vst[to])
                {
                    vst[to] = 1;
                    que[tail++] = to;
                }
            }
            id = y[id].next;
        }
        vst[from] = 0;
        head++;
    }
    long long ans = 0;
    for(int i = 1; i <= v; i++)
        ans += d[i];
    return ans;
}
void insert(int from1, int to1, int va1)
{
    y[cnt].to = to1; y[cnt].value = va1; y[cnt].next = -1;
    if(sta[from1][0] == -1) sta[from1][0] = cnt;
    else y[sta[from1][1]].next = cnt;
    sta[from1][1] = cnt++;
}
int xx[1000000][3];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &v, &e);
        memset(sta, -1, sizeof(sta)); cnt = 0;
        for(int i = 0; i < e; i++)
        {
            scanf("%d%d%d", &xx[i][0], &xx[i][1], &xx[i][2]);
            insert(xx[i][0], xx[i][1], xx[i][2]);
        }
        long long ans = spfa();

        memset(sta, -1, sizeof(sta)); cnt = 0;
        for(int i = 0; i < e; i++)
            insert(xx[i][1], xx[i][0], xx[i][2]);
        ans += spfa();
        cout << ans << endl;
    }
    return 0;
}