9129: Broken Dream

    People comfort and hug each other along the way, where they struggle desperately to chase their broken and dying dream, which has long been an old friend of theirs, since the good old days.
    So does Akura. His dream is also broken now, and he wanted to make it reunited so that he can finally achieve it. From his perspective, his dream has already broken into several islands in the ocean, and there are bridges between some pair of islands, and every bridge has its own length. Akura's task is to find some bridges that connect all these islands while minimizing the total length of the chosen bridges. However, not every bridge is available, there are possibilities that some bridges are broken. So he wants you to help him find the expectation of the total length of bridges you have to choose so that all islands are connected. If in some situations there were no such selection to do so, you don't need to choose any bridges.
    Formally speaking, there are n islands and m bridges. The i−th bridge connects the u_i−th and v_i−th island and has the length of w_i and the possibility of p_i that the bridge is available. Your task is to find the expectation of the total length of the bridges in the MST(minimum spanning tree) modulo 998244353. Note that if in some situations there is no MST in the graph, we consider the total length of bridges in MST to be 0.

    The input consists of multiple test cases. The first line contains a single integer T(1 ≤ T ≤ 7) — the number of test cases.
    The first line of each test case contains 2 integers n, m(n ≤ 15, m ≤ 50).
    The following are m lines.
    The i−th line contains 4 integers u_i, v_i, w_i, p_i (1 ≤ u_i, v_i ≤ n, 0 ≤ w_i < 998244353, 2 ≤ p_i < 998244353), where p_i is the possibility modulo 998244353.

    An integer, the expectation modulo 998244353.

1
3 3
1 2 1 499122177
2 3 2 332748118
3 1 1 499122177

1

    In the example, p₁ = p₃ =1/2, p₂ =1/3.