I think, that 1160 is MST problem. Is my idea correct?
And explain me, please, is my output for sample input correct :
1
3
1 2
2 3
3 4

No, I's not MST. Read problem again.

It's MST, but with another metric.

It's classic MST: all MST with minimum total weight are also ones with minimal weight of the maximal rib. Simple nonmodified Cruscal solve it by ~0.15 sec.