この解説では，以下の 3 ステップに分けて紹介します。
1. グラフの最短経路問題について
2. この問題に最短経路問題をどのように適用するか
3. 解法（サンプルコード：C++, Python）

1. グラフの最短経路問題について

頂点数 \(V\) 辺数 \(E\) の重みつきグラフについて，ある頂点からすべての頂点までの最短路長（最短経路の長さ）を求めるアルゴリズムは，以下のようなものがあります。

Dijkstra（ダイクストラ）法

コストが負の辺が存在しない場合に適用できます。
計算量は \(O((E+V) \log V)\) です。（さらに高速化して \(O(E + V \log V)\) とする方法も存在します。）

詳細については Wikipedia の記事 をご覧ください。

Bellman-Ford（ベルマン-フォード）法

Bellman-Ford 法は，辺のコストが負の場合でも適用できます。また，負閉路が存在する場合でも，それを検出することができます。 計算量は \(O(VE)\) です。

詳細については Wikipedia の記事 をご覧ください。

2. この問題に最短経路問題をどのように適用するか

この問題では，頂点 \(1\) から頂点 \(k\) を経由して，頂点 \(N\) まで至る最短路長を求める必要があります。

各頂点それぞれからすべての頂点への最短路長を求めて，頂点 \(i\) から頂点 \(j\) までの最短路長を \(d_{i,j}\) と表すことにします。この値は，各頂点からダイクストラ法やワーシャルフロイド法を使って求めることができます。
この値を利用すると，頂点 \(k\) に対する答えは \(d_{1,k} + d_{k,N}\) と表すことができます。
しかし，ダイクストラ法を用いる方法では \(O(V(E+V)\log V)\)，ワーシャルフロイド法を用いる方法では \(O(V^3)\) となり，いずれも \(E, V \leq 10^5\) という制約では間に合いません。

ここで，\(d_{1,k} + d_{k,N}\) という式に注目してみましょう。 与えられるグラフは無向グラフであることから，\(d_{i,j} = d_{j,i}\) が成り立ちます。 したがって，\(d_{1,k} + d_{k,N} = d_{1,k} + d_{N,k}\) と変形することができます。
すると，頂点 \(1\) / 頂点 \(N\) から各頂点までの最短路長を求めれば，\(d_{1,k} + d_{N,k}\) の値を求めることができます。

以上の考察より，頂点 \(1\) と頂点 \(N\) のそれぞれからダイクストラ法を適用することで，\(O((E+V)\log V)\) でこの問題を解くことができました。

3. サンプルコード

C++ のサンプルコード

#include <iostream>
#include <queue>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using ll = std::uint64_t;

template <class T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

using Edge = std::pair<int, int>;
using Graph = std::vector<std::vector<Edge>>;

// 頂点 start からダイクストラ法使って各頂点までの最短路長を求める
std::vector<int> dijkstra(const Graph& graph, int start) {
  std::vector<int> dist(graph.size(), 1000000010);
  dist[start] = 0;
  std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pque;
  pque.emplace(0, start);
  while (!pque.empty()) {
    auto [now_cost, now] = pque.top();
    pque.pop();
    if (dist[now] < now_cost) continue;
    for (auto [to, cost] : graph[now]) {
      if (chmin(dist[to], now_cost + cost)) {
        pque.emplace(now_cost + cost, to);
      }
    }
  }
  return dist;
}

int main() {
  int n, m;
  std::cin >> n >> m;
  Graph graph(n);
  rep(i, m) {
    int a, b, c;
    std::cin >> a >> b >> c;
    --a;
    --b;
    graph[a].emplace_back(b, c);
    graph[b].emplace_back(a, c);
  }
  // 頂点 1 からの最短路長
  const auto& from_1 = dijkstra(graph, 0);
  // 頂点 N からの最短路長
  const auto& from_n = dijkstra(graph, n - 1);
  for (int i = 0; i < n; ++i) {
    std::cout << from_1[i] + from_n[i] << "\n";
  }
}

Python のサンプルコード

import heapq


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append((b, c))
        graph[b].append((a, c))

    # 頂点 k からダイクストラ法で各頂点までの最短路長を求める
    def dist_from(k: int):
        pque = []
        dist = [10 ** 9] * n
        dist[k] = 0
        heapq.heappush(pque, (0, k))
        while len(pque) > 0:
            now_cost, now = heapq.heappop(pque)
            if now_cost > dist[now]:
                continue
            for to, cost in graph[now]:
                if now_cost + cost < dist[to]:
                    dist[to] = now_cost + cost
                    heapq.heappush(pque, (now_cost + cost, to))

        return dist

    from_first = dist_from(0)  # 頂点 1 からの最短路長
    from_last = dist_from(n - 1)  # 頂点 N からの最短路長
    for i in range(n):
        print(from_first[i] + from_last[i])


if __name__ == "__main__":
    main()