#include<bits/stdc++.h>
using namespace std;
struct node {
	long long v,w;
};
vector<node>qp[10001];
int n,m;
int vis[10001];
bool op[10001];
bool ok=true;
queue<node>q;
long long dist[10001];
void spfa(){
	memset(dist,63,sizeof(dist));
	dist[0]=0;
	while(q.empty()==0&&ok==true){
		node k=q.front();
		q.pop();
		op[k.v]=false;
		for(int i=0;i<qp[k.v].size();i++){
			if(dist[qp[k.v][i].v]>dist[k.v]+qp[k.v][i].w){
				dist[qp[k.v][i].v]=dist[k.v]+qp[k.v][i].w;
				if(op[qp[k.v][i].v]==false){
                    vis[qp[k.v][i].v]++;
				    if(vis[qp[k.v][i].v]>=n+1){
					   ok=false;
					   break;
				    }										
				    q.push({qp[k.v][i].v,dist[qp[k.v][i].v]});
	                op[qp[k.v][i].v]=true;			    
			    }
				
			}
		}
	}
}
struct node1{
	long long v,w;
	bool operator >(const node1 &A)const{
		return w>A.w;
	}
};
long long u1[10001];
long long v1[10001];
long long w1[10001];
long long h[6001][6001];
vector<node>op1[10001];
bool vis1[6001];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		long long u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		qp[u].push_back({v,w});
		u1[i]=u;
		v1[i]=v;
		w1[i]=w;
	}
	for(int i=1;i<=n;i++){
		qp[0].push_back({i,0});
	
	}
	q.push({0,0});
	spfa();
	if(ok==false){
		printf("-1\n");
		return 0;
    }
    for(int i=1;i<=n;i++){
    	for(int j=0;j<qp[i].size();j++){
    		long long v=qp[i][j].v;
    		long long w=qp[i][j].w;
    		op1[i].push_back({v,w+dist[i]-dist[v]});
		}
	}
	//for(int i=1;i<=m;i++){
	//	op1[u1[i]].push_back({v1[i],w1[i]+dist[u1[i]]-dist[v1[i]]});
//	}
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
	    	h[i][j]=1e9;
		}
		priority_queue<node1,vector<node1>,greater<node1>>lo;
		memset(vis1,false,sizeof(vis1));
		lo.push({i,0});
		h[i][i]=0;
		while(!lo.empty()){
			node1 ki=lo.top();
			lo.pop();
			if(vis1[ki.v]==true){
				continue;
			}
			vis1[ki.v]=true;
			for(int j=0;j<op1[ki.v].size();j++){
				long long v=op1[ki.v][j].v;
				long long w=op1[ki.v][j].w;
				if(h[i][v]>h[i][ki.v]+w){
					h[i][v]=h[i][ki.v]+w;
					if(vis1[v]==false){
					   lo.push({v,h[i][ki.v]});
				    }
				}
			}
		}
		long long ans=0;
		for(int j=1;j<=n;j++){
			if(h[i][j]==1e9){
				ans+=j*1e9;
			}
			else{
				ans+=j*(h[i][j]+dist[j]-dist[i]);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}