#include<fstream> 
using namespace std; 
ifstream in("traseu.in");
ofstream out("traseu.out"); 
const int INF=0x3F3F3F3F; 
int main() 
{int n,m,i,j,k,a[61][61], s=0, c;
	in>>n>>m; 
for(i=1;i<=n;i++) 
	for(j=1;j<=n;j++) 
		if(i==j) a[i][j]=0; 
else a[i][j]=INF; 
	
	while(in>>i>>j>>c) 
	{a[i][j]=c;
	}
	
	for(k=1;k<=n;k++) 
		for(i=1;i<=n;i++) 
			for(j=1;j<=n;j++) 
				if(a[i][j]>a[i][k]+a[k][j]) 
					a[i][j]=a[i][k]+a[k][j]; 
				
				for(i=1;i<n;i++) 
					s+=a[i][i+1];  //drumul de la nodul 1 la 2; de la 2 la 3 etc. n-1...n
                    s+=a[n][1];  //drumul de la nodul n la nodul 1
					
					out<<s; 
}