首先我知道用邻接表肯定会T但是因为懒得写链式前向星，就纯粹想验证一下写对没，结果wa3

QAQ,球大佬找错，跪谢orz

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int inf=1e9;
int n,m;
int edg[3005][3005];
int t[3005];
int vis[3005];
int h[3005];
struct diss{
	ll w;
	int ad;
}dis[3005];
struct cmp{
	    bool  operator ()  (diss  a,diss  b){
	   	      if (a.w<b.w) return false;
	   	      else{
	   	      		if (a.w==b.w) return false;
					else return true; 
				 }
	   } 
};
void init(){
	for (int i=0;i<3005;i++){
		dis[i].w=inf;
		dis[i].ad=i;
		for (int j=0;j<3005;j++){
			edg[i][j]=inf;
		}
	}
}
bool spfa(int s){
	memset(h,63,sizeof(h));
	vis[s]=1;
	h[s]=0;
	t[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for (int i=1;i<=n;i++){
			if (h[i]>h[u]+edg[u][i]){
				h[i]=h[u]+edg[u][i];
				if (!vis[i]){
					vis[i]=1;
					t[i]=t[u]+1;
					if (t[i]>n) return false;
					q.push(i);
				}
			}
		}
	}
	return true;
}
void dj(){
	for (int u=1;u<=n;u++){
		priority_queue<diss,vector<diss>,cmp> q;
		memset(vis,0,sizeof(vis));
		for (int i=1;i<=n;i++) dis[i].w=inf;
		dis[u].w=0;
		q.push(dis[u]);
		while(!q.empty()){
			int x=q.top().ad;
			q.pop();
			if (vis[x]) continue;
			vis[x]=1;
			for (int i=1;i<=n;i++){
				if (edg[x][i]!=inf){
					if (dis[i].w>dis[x].w+(edg[x][i]+h[x]-h[i])){
						dis[i].w=dis[x].w+(edg[x][i]+h[x]-h[i]);
						if (!vis[i])q.push(dis[i]);
					}
				}
			}
		}
//		/*
		ll ans=0;
		for (int i=1;i<=n;i++){
			if (i==u) {
				continue;
			}
			if (dis[i].w==inf){
				ans+=(i*inf);
				continue;
			}
			ans+=(i*(dis[i].w+h[i]-h[u]));
		} 
		cout<<ans<<'\n';
//		*/
		
		/*
		ll ans=0;
		for (int i=1;i<=n;i++){
			if (i==u) {
				continue;
			}
			if (dis[i].w==inf){
				ans+=(i*inf);
				continue;
			}
			ans+=(i*dis[i].w);
		} 
		cout<<ans<<'\n';
		*/
		
		/*
		for (int i=1;i<=n;i++) {
			if (i==u) {
				cout<<0<<' ';
				continue;
			}
			if (dis[i].w==inf){
				cout<<inf<<' ';
				continue;
			}
			cout<<(dis[i].w+h[i]-h[u])<<' ';
		}
		cout<<'\n';
		*/
	}
}
int main(){
	ios::sync_with_stdio(false);
	init();
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int x,y,v;
		cin>>x>>y>>v;
//		edg[x][y]=v;
		if (edg[x][y]>v) edg[x][y]=v;
	}
	for (int i=1;i<=n;i++) edg[0][i]=0;
	
	if (!spfa(0)){
		cout<<-1<<'\n';
		return 0;
	}
	
	dj();
	return 0;
}