154-Journey

#include<bits/stdc++.h>
using namespace std;
const int INF=1000000000;
typedef pair<int,int> pii;
vector<bool> check(105000,false);
vector<int> dis(105000,INF);
vector<pii> G[105000];
priority_queue<pii,vector<pii>,greater<pii>> Q;
int mx;
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    int a,b,c;
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back({c,b});
        G[b].push_back({c,a});
    }
    dis[1]=0;
    Q.push({0,1});
    while(!Q.empty()){
        int u=Q.top().second;
        Q.pop();
        if(dis[u]<=k && u>mx) mx=u;
        if(check[u]) continue;
        check[u]=true;
        for(auto a:G[u]){
            int v=a.second;
            int w=a.first;
            if(!check[v] && dis[v] > dis[u]+w){
                dis[v]=dis[u]+w;
                Q.push({dis[v],v});
            }
        }
    }
    printf("%d",mx);
    return 0;
}