地点 $1$ と地点 $N$ が共にチェックポイントだとしても答えは変わらないのでこれを仮定します。( 出発時と終了時に条件を満たすので )
初めに、各 $2$ 地点間の距離を求めます。これはダイクストラ法を $N$ 回行えばよく $O(NM \log N)$ で可能です。
次に各地点の高さを求めます。入次数が $0$ の頂点を $1$ つ取り、その頂点とそれに接続している辺を全て消す( 実装時は取った頂点から出ている辺の行く先の入次数を $1$ 減らせばよいです )という処理を $N$ 回繰り返して、 $i$ 回目の操作で取った頂点の高さを $i$ とすればよいです。queueなどを使えば $O(N+M)$ で、毎回入次数 $0$ の頂点を $O(N)$ で探しても $O(N^2+M)$ で可能です。

次に、チェックポイントを高さ順にsortします。以降 $T_i$ を $i$ 番目のチェックポイントとして以下のようなDPを考えます。また、 $d(i,j)$ を $T_i$ から $T_j$ への距離とします。( たどり着けないなら $\infty$ )
$dp[i][j]$ $:=$ ( $i \leq j$ として ) $1$ 人が $T_i$ 、もう $1$ 人が $T_j$ にいるかつ $T_1,T_2, \cdots , T_j$ を全て既に踏んでいる場合の距離和の最小値

$dp[1][1]=0$ であり、 答えは$dp[K][K]$ です。 $dp[i][j]$ の寄与は以下のようになります。

• $T_i$ にいる方が $T_{j+1}$ に行く場合 $dp[j][j+1]= \min(dp[j][j+1],dp[i][j]+d(i,j+1))$
• $T_j$ にいる方が $T_{j+1}$ に行く場合 $dp[i][j+1]= \min(dp[i][j+1],dp[i][j]+d(j,j+1))$
• $T_i$ にいる方が $T_{j}$ に行く場合 $dp[j][j]= \min(dp[j][j],dp[i][j]+d(i,j))$

よって、DPの遷移が \(O(1)\) で行えるのでこの問題は全体で \(O(NM \log N)\) で解くことができました。