#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
void read(int &sum)
{
	sum=0;char last='w',ch=getchar();
	while (ch<'0' || ch>'9') last=ch,ch=getchar();
	while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
	if (last=='-') sum=-sum;
}
int n,m;
struct edge { int x,y,c,next; }a[6*100000];
struct t_edge { int x,y,c; }t[6*100000];
struct node { int x,pos; };
priority_queue<node> q;
bool operator <(const node &a,const node &b) { return a.x>b.x; }
int dis[6*100000],vis[6*100000];
int sf[6*100000],went[6*100000],bz[6*100000];
int list[6*100000],head,tail;
int last[6*100000],len;
void ins(int x,int y,int c)
{
	len++;a[len].x=x;a[len].y=y;a[len].c=c;
	a[len].next=last[x];last[x]=len;
}
void spfa(int st)
{
	memset(went,0,sizeof(went));
	memset(sf,63,sizeof(sf));
	list[head]=st;head=1;tail=2;
	sf[st]=0;
	while (head!=tail)
	{
		int x=list[head];bz[x]=false;
		went[x]++;if (went[x]>=n) { printf("-1"); exit(1); }
		for (int k=last[x];k;k=a[k].next)
		{
			int y=a[k].y;
			if (sf[x]+a[k].c<sf[y])
			{
				sf[y]=sf[x]+a[k].c;
				if (bz[y]==false)
				{
					list[tail]=y;bz[y]=true;
					tail++;if (tail>6*100000) tail=1;
				}
			}
		}
		head++;
		if (head>6*100000) head=1;
	}
}
void dijkstr(int st)
{
	for (int i=1;i<=n;i++) dis[i]=1000000000;
	dis[st]=0;q.push((node){0,st});
	memset(vis,false,sizeof(vis));
	while (q.empty()==false)
	{
		int x=q.top().pos;q.pop();
		//printf("%lld\n",x);
		if (vis[x]==true) continue;
		vis[x]=true;
		for (int k=last[x];k;k=a[k].next)
		{
			int y=a[k].y;
			if (dis[x]+a[k].c<dis[y])
			{
				dis[y]=dis[x]+a[k].c;
				q.push((node){dis[y],y});
			}
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		if (dis[i]!=1000000000) dis[i]-=sf[st]-sf[i];
		ans+=dis[i]*i;//printf("%lld ",dis[i]);
	}
	//printf("\n");
	printf("%lld\n",ans);
}
signed main()
{
	//freopen("P5905_5.in","r",stdin);
	//freopen("P5905.out","w",stdout);
	read(n),read(m);
	for (int i=1;i<=m;i++)
	{
		read(t[i].x),read(t[i].y),read(t[i].c);
		ins(t[i].x,t[i].y,t[i].c);
	}
	for (int i=1;i<=n;i++) ins(0,i,0);
	spfa(0);
	//for (int i=1;i<=n;i++) printf("%d ",sf[i]);
	//printf("\n");
	len=0;memset(last,0,sizeof(last));
	for (int i=1;i<=m;i++)
	{
		t[i].c+=sf[t[i].x]-sf[t[i].y];
		//printf("%lld %lld %lld\n",t[i].x,t[i].y,t[i].c);
		ins(t[i].x,t[i].y,t[i].c);
	}
	for (int i=1;i<=n;i++)
		dijkstr(i);
	fclose(stdin);fclose(stdout);
	return 0;
}