There are n houses in Bytetown, labeled by 1,2,...,n. In each house, there is a person living here. Little Q lives in house 1. There are n−1 bidirectional streets connecting these houses, forming a tree structure. In this problem, S(u,v) denotes the house set containing all the houses on the shortest path from house u to house v.

The Bytetown's phone line network consists of m different lines. The i-th line can be expressed as 5 integers ai,bi,ci,di,wi, which means for every two different houses u and v from set S(ai,bi)∪S(ci,di), u and v can have a phone call costing wi dollars.

Picture from Wikimedia Commons

Little Q is now planning to hold a big party in his house, so he wants to make as many as possible people known. Everyone known the message can make several phone calls to others to spread the message, but nobody can leave his house.

Please write a program to figure out the maximum number of people that can join the party and the minimum total cost to reach that maximum number. Little Q should be counted in the answer.

 

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.

In each test case, there are 2 integers n,m(1≤n,m≤100000) in the first line, denoting the number of houses and phone lines.

For the next n−1 lines, each line contains two integers u and v, denoting a bidirectional edge between node u and v.

For the next m lines, each line contains 5 integers ai,bi,ci,di,wi(1≤ai,bi,ci,di≤n,1≤wi≤109), denoting a phone line.

 

For each test case, print a single line containing two integers, denoting the maximum number of people that can join the party and the minimum total cost to reach that maximum number.

 

 

 

#include <bits/stdc++.h>

inline long long read(){long long x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;}

using namespace std;

typedef long long LL;

const int N = 2e5 + , inf = 1e9;

vector<int > G[N];

struct ss{int a,b,c,d,cost;}Q[N];

int cmp(ss s1,ss s2) {return s1.cost < s2.cost;}

int sz[N],dep[N],fa[N],son[N],indexS,top[N],pos[N],ff[N],f[N];

void dfs(int u) {

    int k = ;sz[u] = ;dep[u] = dep[f[u]] + ;

    for(auto to : G[u]) {

        if(to == f[u]) continue;

        f[to] = u;

        dfs(to);

        sz[u] += sz[to];

        if(sz[to] > sz[k]) k = to;

    }

    if(k) son[u] = k;

}

void dfs(int u,int chain) {

    int k = ;pos[u] = ++indexS;

    top[u] = chain;

    if(son[u])

        dfs(son[u],chain);

    for(auto to : G[u]) {

        if(dep[to] > dep[u] && son[u] != to)

            dfs(to,to);

    }

}

int LCA(int x,int y) {

    while(top[x] != top[y]) {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        x = f[top[x]];

    }

    if(dep[x] > dep[y]) swap(x,y);

    return x;

}

LL COST[N],CNT[N];

inline int finds2(int x) {return x == fa[x] ? x:fa[x] = finds2(fa[x]);}

inline int finds(int x) {return x == ff[x] ? x:ff[x] = finds(ff[x]);}

inline void merges(int x,int y,int c) {

        int fx = finds2(x);

        int fy = finds2(y);

        if(dep[fx] < dep[fy]) swap(fx,fy);

        if(fx == fy) return;

        COST[fy] += COST[fx] + c;

        CNT[fy] += CNT[fx];

        fa[fx] = fy;

}

inline void go(int x,int zu,int c) {

    while() {

        x = finds(x);

        if(dep[x] <= dep[zu]) return ;

        merges(x,f[x],c);

        ff[x] = f[x];

    }

}

int n,m,T;

void init() {

    for(int i = ; i <= n; ++i) G[i].clear(),top[i] = ,son[i] = ,dep[i] = ,fa[i] = ,pos[i] = ;

    indexS = ;

}

int main() {

    scanf("%d",&T);

    while(T--) {

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

        init();

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

            int u,v;

            scanf("%d%d",&u,&v);

            G[u].push_back(v);

            G[v].push_back(u);

        }

        dfs();

        dfs(,);

        for(int i = ; i <= n; ++i) fa[i] = ff[i] = i,CNT[i] = ,COST[i] = ;

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

            scanf("%d%d%d%d%d",&Q[i].a,&Q[i].b,&Q[i].c,&Q[i].d,&Q[i].cost);

        sort(Q+,Q+m+,cmp);

        for(int i = ; i <= m; ++i) {

            int lc = LCA(Q[i].a,Q[i].b);

            int lb = LCA(Q[i].c,Q[i].d);

            go(Q[i].a,lc,Q[i].cost);

            go(Q[i].b,lc,Q[i].cost);

            go(Q[i].c,lb,Q[i].cost);

            go(Q[i].d,lb,Q[i].cost);

            merges(lc,lb,Q[i].cost);

            //cout<<lc<<" "<<lb<<endl;

        }

        printf("%lld %lld\n",CNT[finds2()],COST[finds2()]);

    }

    return ;

}