#include <fstream>
#include <algorithm>

#define NMAX 65
#define inf 40000005
using namespace std;

int n;
int deg_bil[NMAX];
int mat[NMAX][NMAX];

ifstream cin("traseu.in");
inline int read(){
    int m=0,s=0;
    cin>>m;

    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            mat[i][j]=inf;
        mat[i][i]=0;
    }

    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        mat[a][b]=min(mat[a][b],c);

        deg_bil[a]--;
        deg_bil[b]++;

        s+=c;
    }

    return s;
}

inline void roy_floyd(){
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(mat[i][k]+mat[k][j]<mat[i][j])
                    mat[i][j]=mat[i][k]+mat[k][j];
}

int cap[NMAX][NMAX];
int cost[NMAX][NMAX];

inline void build_graph(){
    int i,j;
    for(i=1;i<=n;i++)
        if(deg_bil[i]<0)
            cap[i][n+2]=-deg_bil[i];
        else if(deg_bil[i]>0)
            cap[n+1][i]=deg_bil[i];

    roy_floyd();

    for(i=1;i<=n;i++)
        if(deg_bil[i]>0)
            for(j=1;j<=n;j++)
                if(deg_bil[j]<0){
                    cap[i][j]=min(deg_bil[i],-deg_bil[j]);
                    cost[i][j]=mat[i][j];
                    cost[j][i]=-mat[i][j];
                }
}

int dist[NMAX];
int tata[NMAX];

inline bool bf(){
    int i,j,k;

    for(i=1;i<=(n+2);i++)
        dist[i]=inf;
    dist[n+1]=0;

    for(i=1;i<=(n+2);i++)
        for(j=1;j<=(n+2);j++)
            for(k=1;k<=(n+2);k++)
                if(cap[j][k])
                    if(dist[j]+cost[j][k]<dist[k]){
                        dist[k]=dist[j]+cost[j][k];
                        tata[k]=j;
                    }
    return (dist[n+2]!=inf);
}

inline int mincost_maxflow(){
    int ans=0;

    int minim,aux;
    while(bf()){
        minim=cap[tata[n+2]][n+2];
        aux=n+2;

        while(tata[aux]){
            minim=min(minim,cap[tata[aux]][aux]);
            aux=tata[aux];
        }

        aux=n+2;
        while(tata[aux]){
            ans+=cost[tata[aux]][aux]*minim;

            cap[tata[aux]][aux]-=minim;
            cap[aux][tata[aux]]+=minim;

            aux=tata[aux];
        }
    }

    return ans;
}

int main()
{
    ofstream cout("traseu.out");

    cin>>n;

    if(n==1){
        cout<<"0\n";
        return 0;
    }

    int s=0;

    s+=read();
    build_graph();

    cout<<s+mincost_maxflow()<<'\n';

    cin.close();
    cout.close();
    return 0;
}