求调70pts。。。

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N=2*1e5+5;
const int inf=0x3f3f3f3f3f;
int n,m,s,dis[N],dis2[N],ds[N],k;
bool vis[5001][5001];
vector<pair<ll,ll> >v[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
signed main() {
	//freopen("string.in","r",stdin);
	//freopen("string.out","w",stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	cin>>n>>m>>k;
	s=1;
	for(int i=1; i<=m; i++) {
		ll x,y,w;
		cin>>x>>y>>w;
		if(vis[x][y]==0) {
			ds[x]++;
			ds[y]++;
			vis[x][y]==1;
			vis[y][x]==1;
			v[x].push_back(make_pair(y,w));
			v[y].push_back(make_pair(x,w));
		}


	}
	q.push(make_pair(0,1));
	memset(dis,0x3f,sizeof(dis));
	memset(dis2,0x3f,sizeof(dis2));
	dis[s]=0;
	while(!q.empty()) {
		pair<ll,ll> p;
		p=q.top();
		q.pop();
		ll u=p.second,wx=p.first;
		if(p.first>dis2[u])continue;
//		vis[u]=1;
		for(auto& edge : v[u]) {
			ll to = edge.first, w = edge.second;
			ll sw=wx + w;
			if(ds[to]<k&&to!=1&&to!=n)continue;
			if(dis[to] > sw) {
				dis2[to]=dis[to];
				dis[to] = sw;
				q.push(make_pair(sw, to));
			} else if(dis[to] < sw&&dis2[to]>sw) {
				dis2[to] = sw;
				q.push(make_pair(sw, to));
			}
		}
	}
	cout<<dis2[n];
	return 0;
}