制約

入力はすべて単純グラフであるようです．つまり，

• \(city_{i1} \neq city_{i2}\).
• \(i\neq j\) ならば，\(\{city_{i1} \neq city_{i2}\}\neq \{city_{j1} \neq city_{j2}\}\).

が仮定されています．

（問題の不備と考えてよいと思います．「質問」タブに，コンテスト当時は質問への回答という形で対応された痕跡が残っていますが，問題文の修正は行われなかったようです．）

\(M\) の上限が制約が書かれていませんが，単純グラフなので \(77\cdot 21\) 程度でおさえられます．単純グラフの仮定がないと \(M\) がいくらでも大きくなりえてめちゃくちゃです．

テストケース

「最大ケース」に相当するものがなくて，TLE の意味でかなり弱いです．

• \(T=77\times 7\) のケースがない．すべての入力で \(T \leq 470\) 程度になっている．
• 「辺コストの総和」は制約下では最大で \(77\times 21 \times 77\) までありうるが，実際の入力ではすべてその半分以下である．（辺重みは一様乱数と仮定して解いてもよいかもしれません）

なので，あまり真面目に計算量をきちんと検討せずに TLE になりそうな解法でも提出してみると AC になる可能性があると思います．