[email protected] High School Programming Competition 2019


2019-04-13 08:00 AKDT

[email protected] High School Programming Competition 2019


2019-04-13 12:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1133 days 16:53:13

Time elapsed


Time remaining


Problem G

You have crashed your spaceship into a swampy planet. Luckily, you were rescued by a small 900-year-old green alien who lives at the base of a massive tree. Around the tree are many trails which lead to other alien’s houses.

The green alien says he will repair your spaceship if you will help him with a very strange task. “Lots of mist, we have. Hard to see, it is. Help me light up my trails, you will,” the alien says.

The green alien hands you a map of the trail system. There are $n$ houses, each labeled with a unique number between $1$ and $n$, inclusive. There are $m$ trails, each of which goes between a pair of alien’s houses. Each trail is labeled with a unique number between $1$ and $m$, inclusive. The green alien has also marked the length of each of the $m$ trails.

The green alien shows you a reel of wire and a box of light-bulbs. “Be able to visit everyone else on lighted trails, everyone should. Minimum amount of wire and lights, you should use.”

The green alien speaks quite strangely, so it takes a while for you to process this request. Then you realize that the alien wants you to light up the minimum length of trails so that every alien can visit every other alien by travelling only on lighted trails.

Your task is to determine which trails to light up.


The first line contains two integers $n$ and $m$ (in that order).

The subsequent $m$ lines specify information about the $m$ trails labeled on the map, in sorted order (that is, information about trail $1$ is on the first line, trail $2$ on the second line, etc.). Each of the lines contain three integers, $h_1$, $h_2$, and $d$ (in that order). $h_1$ and $h_2$ specify the house numbers of the houses on opposite ends of the trail, and $d$ specifies the trail’s distance.

Input Restrictions

  • All numbers on the same line are space separated.

  • $2 \leq n \leq 100$ and $n - 1 \leq m \leq \frac{n(n - 1)}{2}$

  • For every $h_1$, $h_2$ pair, $h_1 \neq h_2$.

  • All $h_1$ and $h_2$ values are between $1$ and $n$, inclusive.

  • Every $d$ is an integer between $1$ and $100\, 000$, inclusive.

  • You are guaranteed that all of the houses can be connected by a set of trails.

  • You are additionally guaranteed that there is at most one trail between any given $h_1$, $h_2$ pair.


The first line of the output should contain $k$, the number of trails which you need to light up.

The subsequent $k$ lines should contain the numbers corresponding to the trail labels which you need to light up.

Sample Input 1 Sample Output 1
3 3
1 2 1
3 1 2
2 3 1
Sample Input 2 Sample Output 2
8 10
8 4 2
1 7 2
4 3 8
1 2 4
2 3 8
3 6 2
2 6 5
6 5 7
8 1 7
7 3 7