#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N=50050,M=1e4+10;
const int inf=1e9;
int cnt,head[N],nxt[M],to[N];
int n,m,vis[N],num[N];
LL dis[N],dist[N],W[M];
void add(int x,int y,int z){
	to[++cnt]=y;
	W[cnt]=1LL*z;
	nxt[cnt]=head[x];
	head[x]=cnt;
}
bool spfa(int s){
	queue<int> q;
	for(int i=0;i<=n;i++)dis[i]=1e9,vis[i]=0;
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
//			cout<<x<<' '<<y<<endl;
			if(dis[y]>dis[x]+W[i]){
				dis[y]=dis[x]+W[i];
				if(vis[y]==0){
					if(num[y]==n+1) {return false;}
					vis[y]=1;
					q.push(y);
					num[y]++;
				}			
			}
		}
	}
//	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return true;
}
priority_queue<pii,vector<pii>,greater<pii> > q;
void dij(int s){
	for(int i=1;i<=n;i++)dist[i]=inf,vis[i]=0;
	dist[s]=0; vis[s]=1;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int x=q.top().second;
//		cout<<s<<' '<<x<<' '<<dist[x]<<endl;
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			if(dist[y]>dist[x]+W[i]){
				dist[y]=dist[x]+W[i];
				if(vis[y]==0){
					vis[x]=1;q.push(make_pair(dist[y],y));
				}
			}
		}
	}
	LL ans=0;
	for(int i=1;i<=n;i++){
		if(dist[i]==inf) ans+=i*(LL)(1e9); 
		else ans+=i*(dist[i]-dis[s]+dis[i]);
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	freopen("nzq.in","r",stdin);
	freopen("nzq.out","w",stdout); 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z; 
		add(x,y,z);
	}
	for(int i=1;i<=n;i++) add(0,i,0);//,cout<<"fuck!!!"<<0<<' '<<i<<endl;
	if(spfa(0)==0){
		cout<<"-1\n";
		return 0;
	}
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i];
			W[i]+=dis[x]-dis[y];
//			cout<<"???"<<W[i]<<endl;
		}
	}
	for(int i=1;i<=n;i++) dij(i);
	return 0;
}