#include <iostream>

#include <queue>

using namespace std ;

const int INF=0xfffffff ;

struct node{

    int s,t,v,nxt ;

}e[] ;

int n,cnt,head[],vis[],dis[] ;

int rs[],rt[],rv[] ;

void add(int s,int t,int v)

{

    e[cnt].s=s ;

    e[cnt].t=t ;

    e[cnt].v=v ;

    e[cnt].nxt=head[s] ;

    head[s]=cnt++ ;

}

void spfa(int s)

{

    for(int i= ;i<=n ;i++)

        dis[i]=INF ;

    dis[s]= ;

    memset(vis,,sizeof(vis)) ;

    vis[s]= ;

    queue <int> q ;

    q.push(s) ;

    while(!q.empty())

    {

        int u=q.front() ;

        q.pop() ;

        vis[u]= ;

        for(int i=head[u] ;i!=- ;i=e[i].nxt)

        {

            int tt=e[i].t ;

            if(dis[tt]>dis[u]+e[i].v)

            {

                dis[tt]=dis[u]+e[i].v ;

                if(!vis[tt])

                {

                    vis[tt]= ;

                    q.push(tt) ;

                }

            }

        }

    }

}

int main()

{

    int t ;

    scanf("%d",&t) ;

    while(t--)

    {

        cnt= ;

        memset(head,-,sizeof(head)) ;

        int q ;

        scanf("%d%d",&n,&q) ;

        for(int i= ;i<q ;i++)

        {

            scanf("%d%d%d",&rs[i],&rt[i],&rv[i]) ;

            add(rs[i],rt[i],rv[i]) ;

        }

        int ans= ;

        spfa() ;

        for(int i= ;i<=n ;i++)

            ans+=dis[i] ;

        cnt= ;

        memset(head,-,sizeof(head)) ;

        for(int i= ;i<q ;i++)

            add(rt[i],rs[i],rv[i]) ;

        spfa() ;

        for(int i= ;i<=n ;i++)

            ans+=dis[i] ;

        printf("%d\n",ans) ;

    }

    return  ;

}