Minimum Cost to Connect All Districts with Degree Constraint

You are given n districts numbered from 0 to n-1. There are e possible bidirectional roads between these districts; each road connects two different districts and has a specific cost. In addition, each district can have at most m roads connected to it. Your task is to select a subset of the given roads such that all districts are connected (forming a spanning tree) while respecting the degree constraint. If such a configuration is possible, print the minimum total cost; otherwise, print impossible.

The problem can be formalized as follows.

Let \(G=(V,E)\) be an undirected graph with \(|V|=n\) and a set \(E\) of possible edges, where each edge \((u,v)\) has a cost \(w\). You need to choose a subset \(T\) of the edges such that:

• The graph \((V,T)\) is connected and contains exactly \(n-1\) edges (i.e. a spanning tree).
• For every vertex \(v \in V\), the degree of \(v\) in \(T\) does not exceed \(m\).

If such a spanning tree exists, output the sum of the costs of the selected edges, which should be minimum over all valid spanning trees. Otherwise, output impossible.

Note: If any mathematical notation is needed, use LaTeX format (e.g. \(n-1\), \(\le\), etc.).

inputFormat

The first line contains three integers n, m and e separated by spaces, where:

• n is the number of districts.
• m is the maximum number of roads that can be connected to any district.
• e is the number of available roads.

Each of the following e lines contains three integers u, v, and w, representing a road connecting district u and district v with cost w.

outputFormat

If it is possible to connect all districts while satisfying the degree constraint, output a single integer representing the minimum total cost. Otherwise, output impossible.

## sample

4 2 5
0 1 10
0 2 6
0 3 5
1 2 15
2 3 4

19