https://www.luogu.com.cn/record/128336776

// P1359 租用游艇 spfa
// 链式前向星的SPFA 

#include <iostream>
#include <cstring>

using namespace std;

const int N=100000, INF = 0x3f3f3f3f;

int h[N], e[N], w[N], nex[N], idx;// 数组模拟的链表 
int dist[N]; // 距离数组
bool vis[N]; // 是否访问
int n, m;

void add(int a, int b, int v)
{
	e[idx] = b;
	w[idx] = v;
	nex[idx] = h[a];
	h[a] = idx;
	idx++;

 } 

int spfa(int start, int end)
{
	memset(dist, INF, sizeof(dist));
	
	int que[N], f=0, t=0;
	que[++t] = start;	// 入队列 
	dist[start] = 0;	// 距离 
	vis[start] = 1;	// start点添加到队列
	while (f<t)
	{

		int k = que[f+1];
		vis[k] = 0;
		
		for (int i=h[k];i!=-1;i=nex[i])
		{
			int temp = e[i];	// 点
			int val = w[i];	// 权值 
		
			// 判断k加入是否可以更新队列
			if (dist[temp] > dist[k]+val)
			{
				dist[temp] = dist[k]+val;
				if (!vis[temp])
				{
					que[++t] = temp;
					vis[temp] = true;
				}
				
				
			}
		}
		
		f++; // 出队列 
		
	}
	
	
	return dist[end] == INF ? -1 : dist[end];
}


int main()
{
	int a, b, w; // w为权值 
	
	cin >> n >> m;
	
	memset(h, -1, sizeof(h));
	
	for (int i=1;i<=m;i++)
	{

		cin >> a >> b >> w;
		add(a, b, w);


	}	
	
	int t = 0;
	for (int i=2;i<=n;i++)
	{
		memset(vis, 0, sizeof(vis));
		t += spfa(1, i);
		memset(vis, 0, sizeof(vis));
		t += spfa(i, 1);
	}
	


	cout << t;

	
	return 0;
}

球调，难道要用dij？