好像没有严谨证明的题解（可能只是我没有看到），于是我来写一个。
我们假设已经知道第 \(k\) 大的边权为 \(w\)，则我们可以把边权大于等于 \(w\) 的边的边权 \(x\) 全部变成 \(x-w\)，小于 \(w\) 的边权全部变成 \(0\)，再跑最短路。答案就是 \(d_n + k \times w\)。其中 \(d_n\) 表示 \(1 \to n\) 的在新图上的最短路长度。
但是现在我们不知道真正的第 \(k\) 大的边权是多少，我们考虑稀里糊涂的枚举每一条边，把它当作第 \(k\) 大的边权再来跑，得到的结果对答案的影响。
为了方便证明，我们先符号化一下。
按题目中的符号 \(1 \to n\) 的一条路径上有 \(l\) 条边，依次记为 \(c_1,c_2,\cdots,c_l\)，不妨令 \(c_1 \ge c_2 \ge \cdots \ge c_l\)。
真实的答案 \(A= \sum \limits_{i=1} ^k c_i = \sum \limits _{i=1 } ^l \max (c_i -c_k ,0) + k \times c_k\)，我们钦定第 \(t\) 条边为第 \(k\) 大的边后得到的答案 \(A_t = \sum \limits _{i=1 } ^l \max (c_i -c_t ,0) + k \times c_t\)。
- \(c_t = c_k\)，显然 \(A=A_t\)。
- \(c_t < c_k \Rightarrow t>k\)，即我们钦定的这条边更小。
由 \(i \le t \Rightarrow c_i \ge c_t\)，故 \(A \le A_t\)。
- \(c_t > c_k \Rightarrow t < k\)，即我们钦定的边更大。
由 \(i > t \Rightarrow c_i \le c_t\)，故 \(A \le A_t\)。
综上所述，\(\forall 1 \le t \le l,A \le A_t\)，且 \(\exist 1 \le t \le l,A=A_t\)。该结论对于每一条路径都成立，而我们又是在求最短路，所以答案一定能取到。证毕！
用 dijkstra 实现最短路，复杂度为 \(\Theta(m^2 \log n)\)。
最后放一下代码。
#include <bits/stdc++.h>
using namespace std;
const int N=3e3+10;
using ll=long long;
namespace Graph{struct _edge{int v,nxt,w;}es[N*2];int head[N],gcnt;using pii=pair<ll,int>;ll dis[N];bool vis[N];priority_queue<pii,vector<pii>,greater<pii> >pq;void add_edge(int u,int v,int w){es[++gcnt]={v,head[u],w};head[u]=gcnt;}void clear(){memset(head,0,sizeof head);gcnt=0;}void dijkstra(int s){memset(dis,0x3f,sizeof dis);memset(vis,0,sizeof vis);dis[s]=0;pq.emplace(0,s);while(!pq.empty()){int u=pq.top().second;pq.pop();if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=es[i].nxt){int v=es[i].v;if(dis[v]>dis[u]+es[i].w){dis[v]=dis[u]+es[i].w;pq.emplace(dis[v],v);}}}}
}
struct edge{int u,v,w;
}Es[N];
int n,m,K;
int main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m>>K;for(int i=1;i<=m;i++) cin>>Es[i].u>>Es[i].v>>Es[i].w;ll ans=0x3ff3f3f3f3f3f3f;for(int i=0;i<=m;i++){Graph::clear();for(int j=1;j<=m;j++){if(Es[j].w<Es[i].w){Graph::add_edge(Es[j].u,Es[j].v,0);Graph::add_edge(Es[j].v,Es[j].u,0);}else{Graph::add_edge(Es[j].u,Es[j].v,Es[j].w-Es[i].w);Graph::add_edge(Es[j].v,Es[j].u,Es[j].w-Es[i].w);}}Graph::dijkstra(1);ans=min(ans,Graph::dis[n]+1ll*K*Es[i].w);}printf("%lld\n",ans);return 0;
}