考えたこと

素朴にやると「隣接してる頂点の中から最も小さいものを取る」を繰り返せばよい

しかしこの方法だと頂点1から他の10^5個に辺があったときに10^5個からの選択を10^5回くらいするので間に合わない

というわけで毎回検索したりソートしたりしないで最小の値が取れる方法が必要

優先度キューだね