Extrinsically calibrating a multi camera system based on scene images only is in general a very difficult problem. One promising approach computes the extrinsic parameters from sufficiently many pairwise relative poses, which can be reasonably estimated even in case of very many incorrectly matched point correspondences. Obviously, the quality of the calibration highly depends on the correctness of the relative pose estimates. As a limited number of relative poses suffices, we propose automatically selecting only the most reliable ones based on an uncertainty measure. Our selection criterion is equivalent to computing a shortest subgraph consisting of shortest triangle paths. The contribution of this paper consists of a mathematically rigorous proof of the correctness of an efficient algorithm for that problem. In experiments on synthetic and real data, we show that our selection algorithm produces greatly improved calibration results, both, in case of varying portions of outliers as well as varying noise.