洛谷p5905
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int N=3e3+10,INF=1e9;
vector<PII> edges[N];
int dist[N],n,m;
int cnt[N],h[N];
bool st[N];bool spfa(){memset(h,0x3f,sizeof(h));queue<int> q;q.push(0);st[0]=true;h[0]=0;while(q.size()){int u=q.front();q.pop();st[u]=false;for(auto &[v,w]:edges[u]){if(h[v]>h[u]+w){h[v]=h[u]+w;cnt[v]=cnt[u]+1;if(!st[v]){q.push(v);st[v]=true;}if(cnt[v]>=n+1)return false;}}}return true;
}void dijkstra(int s){for(int i=1;i<=n;i++){dist[i]=INF;}auto cmp=[](PII &x,PII &y){return x.second>y.second;};dist[s]=0;priority_queue<PII,vector<PII>,decltype(cmp)> heap(cmp);heap.push({s,0});while(heap.size()){int u=heap.top().first,d=heap.top().second;heap.pop();if(dist[u]<d)continue;for(auto &[v,w]:edges[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;heap.push({v,dist[v]});}}}
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;edges[u].push_back({v,w});}for(int i=1;i<=n;i++){edges[0].push_back({i,0});}if(!spfa()){cout<<-1<<endl;return 0;}for(int u=1;u<=n;u++){for(auto &[v,w]:edges[u]){w+=h[u]-h[v];}}for(int i=1;i<=n;i++){dijkstra(i);LL ans=0;for(int j=1;j<=n;j++){if(dist[j]==INF)ans+=1ll*j*INF;elseans+=1ll*j*(dist[j]+h[j]-h[i]);}cout<<ans<<endl;}return 0;
}