#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
#include<queue>
#include<math.h>
#include<deque>
#include<set>
#include<bitset>
using namespace std;
#define double long double
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define dc(d) double d;cin>>d;
#define mod 100000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
#define pi 3.141592653589793238462643383279
#define e_ 2.718281828459045235360287471352
#define P pair<int,int>
#define upp(a,n,x) upper_bound(a,a+n,x)-a;
#define low(a,n,x) lower_bound(a,a+n,x)-a;
#define pb push_back
struct edge{
	int from;
	int to;
	int cost;
};
int a[114],b[114],c[114];
int d[114];
signed main(){
	ic(n) ic(m)
	vector<edge> e;
	rep(0,i,m){
		struct edge add;
		cin>>a[i]>>b[i]>>c[i];
		add.from=a[i];
		add.to=b[i];
		add.cost=c[i];
		e.pb(add);
	}
	rep(1,p,n+1){
		rep(1,i,n+1)d[i]=inf;
		d[p]=0;
		rep(1,i,n+1){
			rep(0,j,m){
				struct edge f=e[j];
				if(d[f.to]>d[f.from]+f.cost){
					d[f.to]=d[f.from]+f.cost;
				}	
			}	
		}
		int sum=0;
		rep(1,i,n+1){
			if(d[i]!=inf)sum+=d[i];
		}
		c(sum)
	}
}