84pts求条

#include <algorithm>
#include <iostream>
#include <queue>
#define ll long long
using namespace std;
struct Edge
{
	int v;
	ll w;
	bool operator<(const Edge &other) const
	{
		return w > other.w;
	}
};
vector<Edge> to[3005];
ll n, m, d[3005], dis[3005], cnt[3005];
bool inq[3005];
void SPFA()
{
	queue<int> q;
	d[0] = 0, inq[0] = true, q.emplace(0);
	while (!q.empty())
	{
		int now = q.front();
		inq[now] = false, q.pop();
		for (auto e : to[now])
		{
			if (d[e.v] > d[now] + e.w)
			{
				d[e.v] = d[now] + e.w;
				cnt[e.v] = cnt[now] + 1;
				if (cnt[e.v] >= n)
				{
					cout << -1 << endl;
					exit(0);
				}
				if (!inq[e.v])
				{
					inq[e.v] = true, q.emplace(e.v);
				}
			}
		}
	}
}
void Dijkstra(int s)
{
	fill(dis + 1, dis + n + 1, 1000000000ll);
	priority_queue<Edge> pq;
	pq.emplace(Edge{s, 0});
	while (!pq.empty())
	{
		int now = pq.top().v, val = pq.top().w;
		pq.pop();
		if (val > dis[now])
		{
			continue;
		}
		dis[now] = val;
		for (auto e : to[now])
		{
			if (dis[now] + e.w < dis[e.v])
			{
				pq.emplace(Edge{e.v, dis[now] + e.w});
			}
		}
	}
	ll res = 0;
	for (int i = 1; i <= n; i++)
	{
		res += dis[i] * i;
	}
	cout << res << "\n";
	return;
}
ll read();
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read(), w = read();
		to[u].emplace_back(Edge{v, w});
	}
	for (int i = 1; i <= n; i++)
	{
		to[0].emplace_back(Edge{i, 0});
	}
	SPFA();
	for (int i = 1; i <= n; i++)
	{
		Dijkstra(i);
	}
	return 0;
}
ll read()
{
	ll res = 0, w = 1;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-')
		{
			w = -1;
		}
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		res = res * 10 + (c - '0');
		c = getchar();
	}
	return res * w;
}