最短経路問題を解き、駅 \(1\) から駅 \(N\) までの最小運賃と \(K\) との大小を比較すればこの問題に正解できます。

実装例ではダイクストラ法を用いています。

• Wikipedia:ダイクストラ法
• 初心者のためのダイクストラアルゴリズム
• ダイクストラ法（最短経路問題）

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll n,m,k;
  cin >> n >> m >> k;
  vector<vector<pl>> g(n+1);
  for(ll i=0;i<m;i++){
    ll u,v,c;
    cin >> u >> v >> c;
    g[u].push_back({v,c});
    g[v].push_back({u,c});
  }
  vector<ll> d(n+1,4e18);
  priority_queue<pl,vector<pl>,greater<pl>> pq;
  d[1]=0;
  pq.push({0,1});
  while(!pq.empty()){
    auto od=pq.top(); pq.pop();
    if(d[od.second]!=od.first){continue;}
    for(auto [v,c] : g[od.second]){
      if(d[v] > d[od.second]+c){
        d[v]=d[od.second]+c;
        pq.push({d[v],v});
      }
    }
  }

  if(d[n]>k){cout << "-1\n";}
  else{cout << d[n] << "\n";}
  return 0;
}