> 
> 
> 
> 
>      衡水中学的伸手党请出门右拐滏阳河
> 
> 
> 
> #include<cstdio>
> #include<cstring>
> #include<queue>
> #include<con>
> #include<iostream>
> #define MAX_NODE 2010
> #define MAX_LENS 200100
> char c;
> inline void read(int &k){k=0;
> 	do{c=getchar();}while(c<'0'||c>'9');
> 	do{k=k*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
> }
> struct Path{
> 	int to;
> 	int dis;
> 	int next;
> 	Path(){to=-1;dis=0x7ffffff;next=-1;}
> };
> struct Picture{
> 	int from,to,dis;
> }PIC[MAX_LENS];
> struct Node{
> 	long long int f;
> 	int g;
> 	int place;
> 	Node(long long int a=0,int b=0,int c=0):f(a),g(b),place(c){}
> 	bool operator < (const Node &a)const{
> 		return f<a.f;
> 	}
> };
> struct Heap{
> 	int size;
> 	Node table[MAX_LENS*10];
> 	Heap(){size=0;}
> 	void exchange(Node &a,Node &b){
> 		Node c=a;a=b;b=c;
> 	}
> 	bool empty(){return size==0;}
> 	void push(const Node &number){
> 		int place=size;
> 		int last;
> 		table[size]=number;
> 		size++;
> 		while(place!=0){
> 			last=(place-1)>>1;
> 			if(table[place]<table[last])exchange(table[last],table[place]);
> 			else break;
> 			place=last;
> 		}
> 	}
> 	Node pop(){
> 		Node ans=table[0];
> 		table[0]=table[--size];
> 		int t=0;
> 		int l=1,r=2;
> 		while(l<size)
> 		{
> 			if(r<size&&table[r]<table[l])l=r;
> 			if(table[l]<table[t]){exchange(table[t],table[l]);t=l;}
> 			else break;
> 			l=(t<<1|1);r=(t<<1)+2;
> 		}
> 		return ans;
> 	}
> };
> struct Pic{
> 	int lens;
> 	int points;
> 	int len_num;
> 	int cnt[MAX_NODE];
> 	int dis[MAX_NODE];
> 	int head[MAX_NODE];
> 	Path table[MAX_LENS];
> 	Heap q;
> 	Pic(){lens=0;memset(dis,40,sizeof(dis));memset(head,-1,sizeof(head));doing();}
> 	void clean(){
> 		lens=0;memset(head,-1,sizeof(head));memset(table,-1,sizeof(table));
> 	}
> 	void add(const bool &flag=1){
> 		if(flag==1){
> 			for(int i=1;i<=len_num;++i){
> 				table[++lens].next=head[PIC[i].from];
> 				table[lens].to=PIC[i].to;
> 				table[lens].dis=PIC[i].dis;
> 				head[PIC[i].from]=lens;
> 			}
> 		}
> 		else{
> 			for(int i=1;i<=len_num;++i){
> 				table[++lens].next=head[PIC[i].to];
> 				table[lens].to=PIC[i].from;
> 				table[lens].dis=PIC[i].dis;
> 				head[PIC[i].to]=lens;
> 			}
> 		}
> 	}
> 	void dijsa(int from){
> 		dis[from]=0;
> 		q.push(Node(0,0,from));
> 		while(!q.empty()){
> 			Node ppt=q.pop();
> 			if(dis[ppt.place]!=ppt.f)continue;
> 			for(int i=head[ppt.place];i!=-1;i=table[i].next){
> 				if(dis[table[i].to]>dis[ppt.place]+table[i].dis){
> 					dis[table[i].to]=dis[ppt.place]+table[i].dis;
> 					q.push(Node(dis[table[i].to],0,table[i].to));
> 				}
> 			}	
> 		}
> 	}
> 	void A_Star(int from,int to,int Times){
> 		if(from==to)++Times;
> 		while(!q.empty())q.pop();
> 		q.push(Node(dis[from],0,from));
> 		while(!q.empty()){
> 			Node pos=q.pop();
> 			if(pos.place==to){
> 				--Times;
> 				if(Times==0){
> 					std::cout<<pos.g;
> 					return ;
> 				}
> 			}
> 			for(int i=head[pos.place];i!=-1;i=table[i].next){
> 				q.push(Node( dis[table[i].to]+table[i].dis+pos.g, table[i].dis+pos.g ,table[i].to));
> 			}
> 		}
> 		puts("-1");
> 		return;
> 	}
> 	int doing(){
> //		freopen("dota.in","r",stdin);
> //		freopen("dota.out","w",stdout);
> 		read(points);
> 		read(len_num);
> 		int a,b,c,from,to,Times; 
> 		for(int i=1;i<=len_num;++i){
> 			read(a);read(b);read(c);
> 			PIC[i].from=a;
> 			PIC[i].to=b;
> 			PIC[i].dis=c;
> 		}
> 		read(from);read(to);read(Times);
> 		add(0);dijsa(to);
> 		clean();add(1);
> 		A_Star(from,to,Times);
> 		return 0;
> 	}
> }a;
> int main(){;}