گزینه (۳) درست است.

درخت پوشا با وزن بیشینه را در نظر بگیرید. این درخت می‌تواند با الگوریتمی شبیه الگوریتم کروسکال (اگر با آن آشنا نیستید، مطالعه کنید) به دست آید؛ به عبارتی کافی است یال‌ها را به جای از کم‌وزن به پروزن، از پروزن به کم‌وزن مرتّب و الگوریتم را اجرا کنیم. این درخت یک پاسخ برای مسئله است، زیرا به ازای هر دو رأس، عدد هر مسیری بین آن دو از عدد مسیرشان در درخت بیش‌تر نیست (اثبات مانند بهینگی الگوریتم کروسکال). از طرفی مجموع وزن یال‌های یک زیرگراف معتبر نمی‌تواند کم‌تر باشد، زیرا با مرتّب کردن یال‌ها از پروزن به کم‌وزن و بررسی آن‌ها به ترتیب مانند الگوریتم کروسکال، هرگاه یالی از یک وزن باید در درخت بیاید، سازنده‌ی عدد یک مسیر نیز هست و باید بیاید. پس پاسخ برابر مجموع وزن یال‌های این درخت یا همان ۹۵ است.