Assignment of Ancestor Sigils

In the ancient Kingdom of Baiziling, there are \(n\) cities. Each city \(i\) has an ancestor sigil with a positive integer \(w_i\) engraved on it such that \(w_i\in[1,R]\). The \(n\) cities are connected by exactly \(n-1\) bidirectional roads. The \(j\) th road connects city \(u_j\) and city \(v_j\) and comes with an attribute \(t_j\in\{0,1,2\}\) with the following meaning:

• \(t_j=0\): The two cities are enemies, so \(w_{u_j}\) must be different from \(w_{v_j}\).
• \(t_j=1\): The two cities are on equal footing; no condition is imposed on \(w_{u_j}\) and \(w_{v_j}\).
• \(t_j=2\): The two cities are friends, hence \(w_{u_j}\) must equal \(w_{v_j}\).

The road network is guaranteed to be connected. Two sequences \(A=(A_1,A_2,\ldots,A_n)\) and \(B=(B_1,B_2,\ldots,B_n)\) are essentially identical if \(A_i=B_i\) for every \(i\). Your task is to determine:

1. The number of essentially different weight sequences \(w=(w_1,w_2,\ldots,w_n)\) satisfying all the conditions.
2. The minimum possible sum \(\sum_{i=1}^{n}w_i\) among all valid assignments.

Important notes:

• For every road \((p,q,r)\):
• If \(r=0\), then \(w_p\neq w_q\).
• If \(r=1\), no restriction exists between \(w_p\) and \(w_q\).
• If \(r=2\), then \(w_p=w_q\).
• If any condition is unsatisfiable, output 0 for both answers.

Hint: Notice that the roads with \(t=2\) force equality, so you can merge cities into groups. Then, the \(t=0\) roads enforce inequality constraints among these groups. For each connected component (w.r.t. \(t=0\) edges) in the group graph, if it is a tree with \(m\) nodes, there are \(R\cdot (R-1)^{m-1}\) valid assignments. Use a bipartite strategy for computing the minimum sum.

inputFormat

The first line contains two integers \(n\) and \(R\) \( (1\le n\le \text{some limit},\; 1\le R\le \text{some limit})\).

Each of the next \(n-1\) lines contains three integers \(u_j\), \(v_j\), and \(t_j\) describing a road.

outputFormat

Output two space‐separated integers: the number of valid sequences and the minimum sum of \(w_i\) among all valid assignments. If no valid assignment exists, output 0 0.

sample

3 3
1 2 0
2 3 2

6 4