rt，本题除了建边操作外就是最短路板子，而建边操作也很好想，故和最短路模板同难度。