For subtask 1, it suffices to check every possible combination of values for the ~x_i~ against the ~M~ given equations.

Time complexity: ~\mathcal{O}(K^NM)~

For subtasks 2 and 3, we will represent our set of equations as a graph, where each node represents one of the ~N~ variables, and each equation is represented by an edge with a "weight" of ~c_i~, connecting nodes ~a_i~, and ~b_i~. Now, each connected component in our new graph represents a set of variables that are independent of each other. Thus the total number of solutions is the product of the number of solutions for each connected component. For each component, we can also see that if one variable was given a value, it forces a value on all the other variables in the component. We can thus pick an arbitrary variable, ~v~, and solve for the variables in the component in terms of ~v~. We can do this with either BFS or DFS. Each variable can thus have a solution in the form of ~a+v~ or ~a-v~. For each of these, we have ~1 \le x_i \le K~ which places a new restriction on the possible value for ~v~. If a variable has two different representations, we can try to solve for ~v~ which either limits the value of ~v~ to only ~0~ or ~1~ values depending on whether or not there was a contradiction. The number of solutions for this component is thus the number of values of ~v~ that satisfy all the restrictions given by the component. The answer is simply the product of the number of values for each component.

Time complexity: ~\mathcal{O}(N+M)~