#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e3+10, INF=1e9;
ll n, m, hd[N], tot, cnt[N], h[N], dis[N];
bool vis[N];
struct edge{
	ll nt, to, wg;
}e[N<<1];
struct node{
	ll p;
	bool operator<(const node & x) const{
		return dis[p]>dis[x.p];
	}
};
void add(ll u, ll v, ll w){
	e[++tot]={hd[u], v, w};
	hd[u]=tot;
}
bool spfa(){
	queue<ll> q;
	bitset<N> s;
	s.set();
	for(ll i=1; i<=n; ++i) q.push(i);
	while(q.size()){
		ll p=q.front();
		q.pop();
		s[p]=0;
		for(ll i=hd[p], t, w; i; i=e[i].nt){
			t=e[i].to, w=e[i].wg;
			if(h[t]>h[p]+w){
				h[t]=h[p]+w;
				++cnt[t];
				if(cnt[t]==n){
					return 1;
				}
				if(!s[t]){
					s[t]=1;
					q.push(t);
				}
			}
		}
	}
	return 0;
}
void djs(ll p){
	fill(dis, dis+n+1, INF);
	fill(vis, vis+n+1, 0);
	ll ans=0;
	priority_queue<node> pq;
	pq.push({p});
	dis[p]=0;
	while(pq.size()){
		ll tp=pq.top().p;
		pq.pop();
		if(vis[tp]) continue;
		vis[tp]=1;
		for(ll i=hd[tp], t, w; i; i=e[i].nt){
			t=e[i].to, w=e[i].wg; 
			if(dis[t]>dis[tp]+w){
				dis[t]=dis[tp]+w;
				pq.push({t});
			}
		}
	}
	for(ll i=1; i<=n; ++i){
		if(dis[i]==INF) ans+=i*INF;
		else ans+=i*(dis[i]+h[i]-h[p]);
	}
	printf("%lld\n", ans);
}
int main(){
	scanf("%d%d", &n, &m);
	for(ll i=0, u, v, w; i<m; ++i){
		scanf("%lld%lld%lld", &u, &v, &w);
		add(u, v, w);
	}
	
	if(spfa()){
		printf("-1\n");
		return 0;
	}
	for(ll i=1; i<=n; ++i){
		for(ll j=hd[i], t; j; j=e[j].nt){
			t=e[j].to;
			e[j].wg=e[j].wg+h[i]-h[t];
		}
	}
	for(ll i=1; i<=n; i++){
		djs(i);
	}
    return 0;
}