Please help me find the solution to this problem, which basically asks to find MST in grid which goes to all the columns from left to right. We can go to the adjacent cell in the grid (no diagonals).

There can be other solutions but I'm looking for one with Kruskal's or Prim's algorithm. Note that MST always has maximum weight edge as small as possible.

Thanks.