#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define int long long
#define pr pair<int,int>
using namespace std;
const int MA=3006;
const int MAXN=1e9;
int n,m,head[MA],cnt=0,dis[MA],dia[MA],bol[MA],ci[MA],pan=0;
struct zh{
	int x,y,z;
}a[MA*3];
void cuna(int x,int y,int z){
	a[++cnt].x=head[x];a[cnt].y=y;a[cnt].z=z;head[x]=cnt;
}
queue<int> q;
void SPA(){
	for(int i=1;i<=n;i++){
		dis[i]=MAXN;bol[i]=0;
	}
	dis[n+1]=0;bol[n+1]=0;q.push(n+1);
	while(q.empty()==0){
		int x=q.front();q.pop();bol[x]=0;
		for(int i=head[x];i;i=a[i].x){
			int j=a[i].y;
			if(dis[j]>dis[x]+a[i].z){
				dis[j]=dis[x]+a[i].z;
				if(bol[j]==0){
					bol[j]=1;++ci[j];
					if(ci[j]>n){
						printf("-1");pan=1;break;
					}
					q.push(j);
				}
			}
		}
	}
}
priority_queue<pr,vector<pr>,greater<pr> > p;
void DIJ(int s){
	for(int i=1;i<=n;i++){
		dia[i]=MAXN;bol[i]=0;
	}		
	dia[s]=0;bol[s]=1;p.push(make_pair(0,s));
	while(p.empty()==0){
		int x=p.top().second;p.pop();
		for(int i=head[x];i;i=a[i].x){
			if(dia[a[i].y]>dia[x]+a[i].z){
				dia[a[i].y]=dia[x]+a[i].z;
				if(bol[a[i].y]==0){
					bol[a[i].y]=1;p.push(make_pair(dia[a[i].y],a[i].y));
				}
			}			
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(dia[i]==MAXN){
			ans+=1ll*1e9*i; 
		}
		else{
			if(i!=s){
				ans+=1ll*(dia[i]-dis[s]+dis[i])*i;
			}
		}
	}	
	printf("%lld\n",ans);
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		cuna(n+1,i,0);
	}
	for(int i=1;i<=m;i++){
		int	x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
		cuna(x,y,z);
	}
	SPA();
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=a[j].x){
			a[j].z+=dis[i]-dis[a[j].y];
		}
	}	
	if(pan==0){
		for(int i=1;i<=n;i++){
			DIJ(i);
		}
	}
	return 0;
}