#include<bits/stdc++.h>
using namespace std;
const long long N=5e5+1;
long long d[N];
struct a1
{
	long long he,l,r,secondmax,lastmax,firstmax,firstmaxc;
	long long lastmaxsum,flastmaxsum,maxsum,fmaxsum;
}x[N<<2];
void pushup(long long p)
{
	x[p].he=x[p<<1].he+x[p<<1].he;
	x[p].lastmax=max(x[p<<1].lastmax,x[p<<1|1].lastmax);
	x[p].firstmax=max(x[p<<1].firstmax,x[p<<1|1].firstmax);
	if(x[p<<1].firstmax==x[p<<1|1].firstmax)
	{
	    x[p].firstmaxc=x[p<<1].firstmaxc+x[p<<1|1].firstmaxc;
		x[p].secondmax=max(x[p<<1].secondmax,x[p<<1|1].secondmax);	
	}
	if(x[p<<1].firstmax>x[p<<1|1].firstmax)
	{
		x[p].firstmaxc=x[p<<1].firstmaxc;
		x[p].secondmax=max(x[p<<1].secondmax,x[p<<1|1].firstmax);
	}
	if(x[p<<1].firstmax<x[p<<1|1].firstmax)
	{
		x[p].firstmaxc=x[p<<1|1].firstmaxc;
		x[p].secondmax=max(x[p<<1].firstmax,x[p<<1|1].secondmax);
	}
}
void pushdown(long long p)
{
	long long maxx=max(x[p<<1].firstmax,x[p<<1|1].firstmax);
	if(x[p<<1].firstmax==maxx)
	{
		x[p<<1].he+=x[p].maxsum*x[p<<1].firstmaxc+(x[p<<1].r-x[p<<1].l+1-x[p<<1].firstmaxc)*x[p].fmaxsum;
		x[p<<1].lastmax=max(x[p<<1].lastmax,x[p<<1].firstmax+x[p].lastmaxsum);
		x[p<<1].firstmax+=x[p].maxsum;
		if(x[p<<1].secondmax!=-1e16)
		{
			x[p<<1].secondmax+=x[p].fmaxsum;
		}
		x[p<<1].lastmaxsum=max(x[p<<1].lastmaxsum,x[p<<1].maxsum+x[p].lastmaxsum);
		x[p<<1].flastmaxsum=max(x[p<<1].flastmaxsum,x[p<<1].fmaxsum+x[p].flastmaxsum);
	    x[p<<1].maxsum+=x[p].maxsum;
	    x[p<<1].fmaxsum+=x[p].fmaxsum;
	}
	else
	{
		x[p<<1].he+=(x[p<<1].r-x[p<<1].l+1)*x[p].fmaxsum;
		x[p<<1].lastmax=max(x[p<<1].lastmax,x[p<<1].firstmax+x[p].flastmaxsum);
		x[p<<1].firstmax+=x[p].fmaxsum;
		if(x[p<<1].secondmax!=-1e16)
		{
			x[p<<1].secondmax+=x[p].fmaxsum;
		}
		x[p<<1].lastmaxsum=max(x[p<<1].lastmaxsum,x[p<<1].maxsum+x[p].flastmaxsum);
		x[p<<1].flastmaxsum=max(x[p<<1].flastmaxsum,x[p<<1].fmaxsum+x[p].flastmaxsum);
	    x[p<<1].maxsum+=x[p].fmaxsum;
	    x[p<<1].fmaxsum+=x[p].fmaxsum;
	}
	if(x[p<<1|1].firstmax==maxx)
	{
		x[p<<1|1].he+=x[p].maxsum*x[p<<1|1].firstmaxc+(x[p<<1|1].r-x[p<<1|1].l+1-x[p<<1|1].firstmaxc)*x[p].fmaxsum;
		x[p<<1|1].lastmax=max(x[p<<1|1].lastmax,x[p<<1|1].firstmax+x[p].lastmaxsum);
		x[p<<1|1].firstmax+=x[p].maxsum;
		if(x[p<<1|1].secondmax!=-1e16)
		{
			x[p<<1|1].secondmax+=x[p].fmaxsum;
		}
		x[p<<1|1].lastmaxsum=max(x[p<<1|1].lastmaxsum,x[p<<1|1].maxsum+x[p].lastmaxsum);
		x[p<<1|1].flastmaxsum=max(x[p<<1|1].flastmaxsum,x[p<<1|1].fmaxsum+x[p].flastmaxsum);
	    x[p<<1|1].maxsum+=x[p].maxsum;
	    x[p<<1|1].fmaxsum+=x[p].fmaxsum;
	}
	else
	{
		x[p<<1|1].he+=(x[p<<1|1].r-x[p<<1|1].l+1)*x[p].fmaxsum;
		x[p<<1|1].lastmax=max(x[p<<1|1].lastmax,x[p<<1|1].firstmax+x[p].flastmaxsum);
		x[p<<1|1].firstmax+=x[p].fmaxsum;
		if(x[p<<1|1].secondmax!=-1e16)
		{
			x[p<<1|1].secondmax+=x[p].fmaxsum;
		}
		x[p<<1|1].lastmaxsum=max(x[p<<1|1].lastmaxsum,x[p<<1|1].maxsum+x[p].flastmaxsum);
		x[p<<1|1].flastmaxsum=max(x[p<<1|1].flastmaxsum,x[p<<1|1].fmaxsum+x[p].flastmaxsum);
	    x[p<<1|1].maxsum+=x[p].fmaxsum;
	    x[p<<1|1].fmaxsum+=x[p].fmaxsum;
	}
	x[p].lastmaxsum=0;
	x[p].flastmaxsum=0;
	x[p].maxsum=0;
	x[p].fmaxsum=0;
}
void build(long long l,long long r,long long p)
{
	x[p].l=l;x[p].r=r;
	if(l==r)
	{
		x[p].he=d[l];
		x[p].firstmax=d[l];
		x[p].lastmax=d[l];
		x[p].secondmax=-1e16;
		x[p].lastmaxsum=0;
		x[p].flastmaxsum=0;
		x[p].maxsum=0;
		x[p].fmaxsum=0;
		x[p].firstmaxc=1;
		return ;
	}
	long long mid=(l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	pushup(p);
}
void jj(long long l,long long r,long long p,long long k)
{
	if(x[p].l>=l&&x[p].r<=r)
	{
		x[p].he+=k*(x[p].r-x[p].l+1);
		x[p].firstmax+=k;
		x[p].lastmax=max(x[p].lastmax,x[p].firstmax);
		if(x[p].secondmax!=-1e16)x[p].secondmax+=k;
		x[p].maxsum+=k;
		x[p].lastmaxsum=max(x[p].maxsum,x[p].lastmaxsum);
		x[p].fmaxsum+=k;
		x[p].flastmaxsum=max(x[p].fmaxsum,x[p].flastmaxsum);
		return ;
	}
	pushdown(p);
	if(x[p<<1].r>=l)jj(l,r,p<<1,k);
	if(x[p<<1|1].l<=r)jj(l,r,p<<1|1,k);
	pushup(p);
}
void min(long long l,long long r,long long p,long long k)
{
	if(x[p].firstmax<=k)return ;
	if(x[p].l>=l&&x[p].r<=r&&x[p].secondmax<k)
	{
		x[p].he=x[p].he-(x[p].firstmax-k)*x[p].firstmaxc;
		x[p].maxsum=x[p].maxsum-x[p].firstmax+k;
		x[p].lastmaxsum=max(x[p].maxsum,x[p].lastmaxsum);
		x[p].firstmax=k;
		x[p].lastmax=max(x[p].lastmax,x[p].firstmax);
		return ;
	}
	pushdown(p);
	if(x[p<<1].r>=l)min(l,r,p<<1,k);
	if(x[p<<1|1].l<=r)min(l,r,p<<1|1,k);
	pushup(p);
}
long long getsum(long long l,long long r,long long p)
{
	if(x[p].l>=l&&x[p].r<=r)
	{
		return x[p].he;
	}
	pushdown(p);
	long long ans=0;
	if(x[p<<1].r>=l)ans+=getsum(l,r,p<<1);
	if(x[p<<1|1].l<=r)ans+=getsum(l,r,p<<1|1);
	return ans;
}
long long getmax(long long l,long long r,long long p)
{
	if(x[p].l>=l&&x[p].r<=r)
	{
		return x[p].firstmax;
	}
	pushdown(p);
	long long maxx=-1e16;
	if(x[p<<1].r>=l)maxx=max(getmax(l,r,p<<1),maxx);
	if(x[p<<1|1].l<=r)maxx=max(getmax(l,r,p<<1|1),maxx);
    return maxx;
}
long long getlastmax(long long l,long long r,long long p)
{
	if(x[p].l>=l&&x[p].r<=r)
	{
		return x[p].lastmax;
	}
	pushdown(p);
	long long maxx=-1e16;
	if(x[p<<1].r>=l)maxx=max(getlastmax(l,r,p<<1),maxx);
	if(x[p<<1|1].l<=r)maxx=max(getlastmax(l,r,p<<1|1),maxx);
    return maxx;
}
inline long long read()
{
	long long x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}//以上是吉司机线段树
struct a2
{
	long long l,r,a;
	a2(){a=0;} 
}xx[5000001];
long long t=1;
void pushpup(long long p){xx[p].a=xx[xx[p].l].a+xx[xx[p].r].a;}
void insert(long long l,long long r,long long p,long long a)
{
	if(l==r)
	{
		xx[p].a++;
		return ;
	}
	long long mid=(l+r)>>1;
	if(a<=mid)
	{
	 	if(xx[p].l==0)
	    {
		   xx[p].l=++t;
	    }
	    insert(l,mid,xx[p].l,a);
	}
	else
	{
		if(xx[p].r==0)
	    {
		   xx[p].r=++t;
	    }
	    insert(mid+1,r,xx[p].r,a);
	}
	pushpup(p);
}
void cut(long long l,long long r,long long p,long long a)
{
	if(l==r)
	{
		xx[p].a--;
		return ;
	}
	long long mid=(l+r)>>1;
	if(a<=mid)
	{
	 	if(xx[p].l==0)
	    {
		   xx[p].l=++t;
	    }
	    cut(l,mid,xx[p].l,a);
	}
	else
	{
		if(xx[p].r==0)
	    {
		   xx[p].r=++t;
	    }
	    cut(mid+1,r,xx[p].r,a);
	}
	pushpup(p);
}
long long query1(long long l,long long r,long long p,long long a)
{
	if(l==r)
	{
		return 1;
	}
	long long mid=(l+r)>>1;
	if(a>mid)
	{
		if(xx[p].r==0)
	    {
		   xx[p].r=++t;
	    }
	    return xx[xx[p].l].a+query1(mid+1,r,xx[p].r,a);
	}
	else
	{
		if(xx[p].l==0)
	    {
		   xx[p].l=++t;
	    }
	    return query1(l,mid,xx[p].l,a);
	}
	pushpup(p);
}
long long query2(long long l,long long r,long long p,long long a)
{
	if(l==r)
	{
		return l;
	}
	long long mid=(l+r)>>1;
	if(a-xx[xx[p].l].a<=0)
	{
	 	if(xx[p].l==0)
	    {
		   xx[p].l=++t;
	    }
	    return query2(l,mid,xx[p].l,a);
	}
	else
	{
		if(xx[p].r==0)
	    {
		   xx[p].r=++t;
	    }
	    return query2(mid+1,r,xx[p].r,a-xx[xx[p].l].a);
	}
	pushpup(p);
}//以上为权值线段树模拟平衡树。
struct bigint{
	long long a[500001],len,ff;
	bigint(){memset(a,0,sizeof(a));len=0;ff=0;}
    friend void read(bigint &A)
    {
        char c=getchar();
        while(c>'9'||c<'0')c=getchar();
        while(c>='0'&&c<='9'){A.a[++A.len]=c-'0';c=getchar();}
        reverse(A.a+1,A.a+1+A.len);
    }
    friend void putb(bigint Z)
    {
        if(Z.len==0)putchar('0');
        else 
        {
            if(Z.ff==1)putchar('-');
            for(register long long i=Z.len;i>=1;i--)putchar(Z.a[i]+'0');
        }
        return;
    }
	friend bigint up(bigint A,long long w)
	{
		bigint C;C.len=A.len+w;
		for(register long long i=1;i<=A.len;i++)C.a[i+w]=A.a[i];
		return C;
	}
	friend bigint operator + (const bigint &A,const bigint &B)
	{
		bigint C;
		long long m=A.len>B.len?A.len:B.len;
		for(register long long i=1;i<=m;i++)
		{
			C.a[i]+=A.a[i]+B.a[i];
			C.a[i+1]+=C.a[i]/10;
			C.a[i]%=10;
		}
		C.len=C.a[m+1]>0?m+1:m;
		return C;
	}
	friend bool operator > (const bigint &A,const bigint &B)
	{
		if(A.len>B.len)return 1;
		else if(A.len<B.len)return 0;
		else
		{
			for(register long long i=A.len;i>=1;i--)
			{
				if(A.a[i]>B.a[i])return 1;
				else if(A.a[i]<B.a[i])return 0;
			}
			return 0;
		}
	}
	friend bigint operator - (const bigint &A,const bigint &B)
	{
		bigint C;
		long long m=A.len>B.len?A.len:B.len;
		if(B>A)
		{
			C.ff=1;
			for(register long long i=1;i<=m;i++)
			{
				C.a[i]+=B.a[i]-A.a[i];
				if(C.a[i]<0){C.a[i+1]--;C.a[i]+=10;}
			}
		}
		else
		{
			for(register long long i=1;i<=m;i++)
			{
				C.a[i]+=A.a[i]-B.a[i];
				if(C.a[i]<0){C.a[i+1]--;C.a[i]+=10;}
			}
		}
		while(C.a[m]==0&&m>0)m--;
		C.len=m;
		return C;
	}
	friend bigint operator * (const bigint &A,const long long &b)
	{
		bigint C;C.len=A.len;
		for(register long long i=1;i<=A.len;i++)
		{
			C.a[i]+=A.a[i]*b;
			C.a[i+1]+=C.a[i]/10;
			C.a[i]%=10;
		}
		while(C.a[C.len+1])
		{
			C.len++;
			C.a[C.len+1]+=C.a[C.len]/10;
			C.a[C.len]%=10;
		}
        while(C.a[C.len]==0&&C.len>0)C.len--;
		return C;
	}
	friend bigint operator * (const bigint &A,const bigint &B)
	{
		bigint C;
		long long m=A.len+B.len;
		for(register long long i=1;i<=A.len;i++)
		{
			for(long long j=1;j<=B.len;j++)
			{
				C.a[i+j-1]+=A.a[i]*B.a[j];
				C.a[i+j]+=C.a[i+j-1]/10;
				C.a[i+j-1]%=10;
			}
		}
		while(C.a[m]==0&&m>0)m--;
		C.len=m;
		return C;
	}
	friend bigint operator / (const bigint &A,const long long &b)
    {
        bigint C;
        long long m=A.len,x=0;
        for(register long long i=m;i>=1;i--)
        {
            x=x*10+A.a[i];
            C.a[i]=x/b;
            x%=b;
        }
        while(C.a[m]==0&&m>0)m--;
        C.len=m;
        return C;
    }
    friend bigint operator / (const bigint &A,const bigint &B)
    {
        bigint C,Z=A;
        long long m=max(A.len-B.len+1,1ll);
        for(register long long i=m;i>=1;i--)
        {
            bigint x=up(B,i-1);
            while(!(x>Z)){Z=Z-x;C.a[i]++;}
        }
        while(C.a[m]==0&&m>0)m--;
        C.len=m;
        return C;
    }
    friend bigint operator % (const bigint &A,const bigint &B)
    {
        bigint C,Z=A;
        long long m=max(A.len-B.len+1,1ll);
        for(register long long i=m;i>=1;i--)
        {
            bigint x=up(B,i-1);
            while(!(x>Z)){Z=Z-x;C.a[i]++;}
        }
        while(C.a[m]==0&&m>0)m--;
        C.len=m;
        return Z;
    }
};//以上为高精全套板子万能
namespace w{
	struct a1
	{
		int to,nex,dis,l;
	}x[3000001];
	int head[3000001],l[1000001],pre[100001][3],p=1,n,m;
	void add(int a,int b,int c,int d)
	{
		x[++p].nex=head[a];
		x[p].to=b;
		x[p].l=c;
		x[p].dis=d;
		head[a]=p;
		return ;
	}
	int s,t,ans1,ans2;
	int k[100001],dis[100001],v[300001],diss[300001];
	int spfa()
	{
		queue<int>z;
		fill(k,k+1+n,0);
		fill(v,v+1+n+n,0);
		z.push(s);
		fill(dis+1,dis+1+n,1e9);
		dis[s]=0;
		l[s]=1e9;
		pre[s][1]=-1;
		pre[s][2]=-1;
		v[s]=1;
		while(!z.empty())
		{
			int i=z.front();
			z.pop();
			v[i]=0;
			for(int q=head[i];q;q=x[q].nex)
			{
				int o=x[q].to;
				int d=x[q].dis;
				if(!x[q].l)continue;
	//			if(k[o]>=n+30)return 0;
				if(x[q].l!=0&&dis[o]>dis[i]+d)
				{
					l[o]=min(l[i],x[q].l);
					pre[o][2]=q;
					pre[o][1]=i;
					dis[o]=dis[i]+d;
					if(v[o]==0){v[o]=1;z.push(o);}
				}
			}
		}
		if(dis[t]==1e9)return 0;
		else
		{
			int p=1e9;
			for(int i=t;i!=s;i=pre[i][1])
			{
				x[pre[i][2]^1].l+=l[t];
				x[pre[i][2]].l-=l[t];
			}
			ans1+=l[t];
			ans2+=dis[t]*l[t];
			return 1;
		}
	}
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
}//以上为最小费用最大流
namespace WW{
	struct a1
	{
		int to,nex,dis,l;
	}x[3000001];
	int head[3000001],l[1000001],pre[100001][3],p=1,n,m;
	void add(int a,int b,int c,int d)
	{
		x[++p].nex=head[a];
		x[p].to=b;
		x[p].l=c;
		x[p].dis=d;
		head[a]=p;
		return ;
	}
	int s,t,ans1,ans2;
	int k[100001],dis[100001],v[300001],diss[300001];
	int spfa()
	{
		queue<int>z;
		fill(k,k+1+n+n,0);
		fill(v,v+1+n+n,0);
		z.push(s);
		fill(dis+1,dis+1+n+n,1e9);
		dis[s]=0;
		l[s]=1e9;
		pre[s][1]=-1;
		pre[s][2]=-1;
		v[s]=1;
		while(!z.empty())
		{
			int i=z.front();
			z.pop();
			v[i]=0;
			for(int q=head[i];q;q=x[q].nex)
			{
				int o=x[q].to;
				int d=x[q].dis;
				if(x[q].l>0&&dis[o]>dis[i]+d)
				{
					l[o]=min(l[i],x[q].l);
					pre[o][2]=q;
					pre[o][1]=i;
					dis[o]=dis[i]+d;
					if(v[o]==0){v[o]=1;z.push(o);}
				}
			}
		}
		if(dis[t]==1e9)return 0;
		else
		{
			int p=1e9;
			for(int i=t;i!=s;i=pre[i][1])
			{
				x[pre[i][2]^1].l+=l[t];
				x[pre[i][2]].l-=l[t];
			}
			ans1+=l[t];
			ans2+=dis[t]*l[t];
			return 1;
		}
	}
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
}//以上为网络流EK。
namespace DD{
	using namespace std;
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	struct a1
	{
		int nex,to,dis;
	}x[1000001];
	int head[1000001],p=0,dis[1000001],v[1000001],s[1000001];
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >z;
	void a2(int a,int b,int c)
	{
		x[++p].nex=head[a];
		x[p].to=b;
		x[p].dis=c;
		head[a]=p;
	}
	int mmain()
	{
		int n,m,k;
		n=read();m=read();k=read();
		for(int q=1;q<=k;q++)
		{
			int a;
			a=read();
			s[a]=1;
		}
		for(int q=1;q<=m;q++)
		{
			int a,b,c;
			a=read();b=read();c=read();
			a2(a,b,c);
			a2(b,a,c);
		}
		int x1,x2;
		cin>>x1>>x2;
		
		z.push(make_pair(0,1));
	    fill(dis,dis+1+n,1e9);
	    fill(v,v+1+n,0);
		dis[1]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
		    for(register int q=head[i];q;q=x[q].nex)
		    {
			   	int o=x[q].to;
			   	if(dis[o]>dis[i]+x[q].dis)
			   	{
		    		dis[o]=dis[i]+x[q].dis;
		    		z.push(make_pair(dis[o],o));
		    	}
	    	}  	
	   	}  
	   	int x1p=dis[x1],x2p=dis[x2];//哈利 
		   
		z.push(make_pair(0,1));
	    fill(dis,dis+1+n,1e9);
	    fill(v,v+1+n,0);
		dis[1]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
		    for(register int q=head[i];q;q=x[q].nex)
		    {
			   	int o=x[q].to;
			   	if(s[o]==1)continue;
			   	if(dis[o]>dis[i]+x[q].dis)
			   	{
		    		dis[o]=dis[i]+x[q].dis;
		    		z.push(make_pair(dis[o],o));
		    	}
	    	}  	
	   	}  
		int x1k=dis[x1],x2k=dis[x2];
		
		z.push(make_pair(0,x1));
	    fill(dis,dis+1+n,1e9);
	    fill(v,v+1+n,0);
		dis[x1]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
		    for(register int q=head[i];q;q=x[q].nex)
		    {
			   	int o=x[q].to;
			   	if(dis[o]>dis[i]+x[q].dis)
			   	{
		    		dis[o]=dis[i]+x[q].dis;
		    		z.push(make_pair(dis[o],o));
		    	}
	    	}  	
	   	}  
	   	int x2p2=dis[x2];//哈利 
	   	
	   	z.push(make_pair(0,x2));
	    fill(dis,dis+1+n,1e9);
	    fill(v,v+1+n,0);
		dis[x2]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
		    for(register int q=head[i];q;q=x[q].nex)
		    {
			   	int o=x[q].to;
			   	if(dis[o]>dis[i]+x[q].dis)
			   	{
		    		dis[o]=dis[i]+x[q].dis;
		    		z.push(make_pair(dis[o],o));
		    	}
	    	}  	
	   	}  
	   	int x1p2=dis[x1];//哈利 
	   	
	   	z.push(make_pair(0,x1));
	    fill(dis,dis+1+n,1e9);
	    fill(v,v+1+n,0);
		dis[x1]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
		    for(register int q=head[i];q;q=x[q].nex)
		    {
			   	int o=x[q].to;
			   	if(s[o]==1)continue;
			   	if(dis[o]>dis[i]+x[q].dis)
			   	{
		    		dis[o]=dis[i]+x[q].dis;
		    		z.push(make_pair(dis[o],o));
		    	}
	    	}  	
	   	}  
		int x2k2=dis[x2];
		
		z.push(make_pair(0,x2));
	    fill(dis,dis+1+n,1e9);
	    fill(v,v+1+n,0);
		dis[x2]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
		    for(register int q=head[i];q;q=x[q].nex)
		    {
			   	int o=x[q].to;
			   	if(s[o]==1)continue;
			   	if(dis[o]>dis[i]+x[q].dis)
			   	{
		    		dis[o]=dis[i]+x[q].dis;
		    		z.push(make_pair(dis[o],o));
		    	}
	    	}  	
	   	}  
		int x1k2=dis[x1];
	
		int ans1=max(x1k,x2p),ans2=max(x1p,x2k),ans3=min(x1k2+x2k,x2k2+x1k),ans4=min(x1p2+x2p,x2p2+x1p);
		
		cout<<min(min(ans1,ans2),min(ans3,ans4));   
		return 0;
	}
}//以上为单元最短路
namespace MM{
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	struct a1
	{
		int to,nex,dis,s;
	}x[1000001];
	int head[1000001],v[1000001],dis[1000001],p=0,lu[1001][5001];
	void a2(int a,int b,int c)
	{
		x[++p].nex=head[a];
		x[p].to=b;
		x[p].dis=c;
		x[p].s=p;
		head[a]=p;
		return ;
	}
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >z;
	int main()
	{
		int n,m;
		n=read();m=read();
		for(register int q=1;q<=m;q++)
		{
			int a,b,c;
			a=read();b=read();c=read();
			a2(a,b,c);
			a2(b,a,c);
		}
		z.push(make_pair(0,n));
		fill(dis,dis+1+n,1e9);
		fill(v,v+1+n,0);
		dis[n]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			if(v[i]==1)continue;
			v[i]=1;
			for(register int q=head[i];q;q=x[q].nex)
			{
				int o=x[q].to;
	//			cout<<q<<endl;
				if(dis[o]>dis[i]+x[q].dis)
				{
					dis[o]=dis[i]+x[q].dis;
					for(int w=0;w<=lu[i][0];w++)lu[o][w]=lu[i][w];
					lu[o][0]++;lu[o][lu[o][0]]=x[q].s;
					z.push(make_pair(dis[o],o));
				}
			}
		}
		long long k=dis[1],ans=0;
	//	cout<<dis[n];
	//	for(int q=1;q<=lu[n][0];q++)cout<<lu[n][q]<<" ";
	    for(register int q=lu[1][0];q>=1;q--)
	    {
	    	int h=x[lu[1][q]].dis;
	    	x[lu[1][q]].dis=1e9;
	    	z.push(make_pair(0,n));
	    	fill(dis,dis+1+n,1e9);
		    fill(v,v+1+n,0);
		    dis[n]=0;
		    while(!z.empty())
		    {
		    	if(clock()>=997000)
		        {
		    	cout<<ans;
		    	return 0;
			   }
			    int i=z.top().second;
			    z.pop();
			    if(v[i]==1)continue;
			    v[i]=1;
		    	for(register int q=head[i];q;q=x[q].nex)
		    	{
			    	int o=x[q].to;
	//		    	cout<<q<<endl;
			    	if(dis[o]>dis[i]+x[q].dis)
			    	{
			    		dis[o]=dis[i]+x[q].dis;
			    		z.push(make_pair(dis[o],o));
			    	}
		    	}  	
	    	}
	    	long long l=dis[1];
		    ans=max(ans,l);
		    x[lu[1][q]].dis=h;
		    if(clock()>=995000)
		    {
		    	cout<<ans;
		    	return 0;
			}
	    }
	    cout<<ans;
		return 0;
	}
}
namespace TT{
	struct a1
	{
		int to,nex,dis;
	}x[1009001];
	int head[1009001],p=0,v[1009001],vis[1009001],dis[1009001];
	void a2(int a,int b)
	{
		x[++p].nex=head[a];
		x[p].to=b;
		head[a]=p;
		return ;
	}
	int n,m,k,s,P,Q,a1[1000901],a[1009000],b[1009001];
	priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > >z;
	queue<int >l;
	void bfs(int a)
	{
		l.push(a);
		return ;
	}
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	int mmmain()
	{
	//	freopen("11.in","r",stdin);
	//	freopen("1.out","w",stdout);
	n=read();m=read();k=read();s=read();P=read();Q=read();
	//	cin>>n>>m>>k>>s;
	//	cin>>P>>Q;
		for(int q=1;q<=k;q++)
		{
			a1[q]=read();
	        vis[a1[q]]=1;
		}
		for(int w=1;w<=m;w++)
		{
			a[w]=read();b[w]=read();
	//		cin>>a[w]>>b[w];
	        a2(a[w],b[w]);
	        a2(b[w],a[w]);
		}
	    fill(v,v+1+n,1e9);
	    for(int q=1;q<=k;q++)
		{
			bfs(a1[q]);
			v[a1[q]]=0;
		}
		while(!l.empty())
		{
			int i=l.front();
			l.pop();
			for(int q=head[i];q;q=x[q].nex)
			{
				int o=x[q].to;
				if(v[o]>v[i]+1&&v[i]+1<=s)
				{
					v[o]=v[i]+1;
					l.push(o);
				}
			}
		}
	   // for(int q=1;q<=n;q++)
	   // {
	   // if(v[q]!=1e9)cout<<q<<" ";
	    //}
	    //cout<<"\n";
	    for(int w=1;w<=m;w++)
		{
	        int c;
			if(v[b[w]]!=1e9)x[2*w-1].dis=Q;
			else x[2*w-1].dis=P;
			if(v[a[w]]!=1e9)x[2*w].dis=Q;
			else x[2*w].dis=P;
			if(b[w]==n)x[2*w-1].dis=0;
			if(a[w]==n)x[2*w].dis=0;
	//        if(b[w]==1)x[2*w-1].dis=0;
	//        if(a[w]==1)x[2*w].dis=0;
		}
	   // for(int q=1;q<=2*m;q++)
	  // {
	      //  cout<<x[q].to<<" "<<x[q].dis<<"\n";
	  //  }
		fill(dis,dis+1+n,1e18);
		z.push(make_pair(0,1));
		dis[1]=0;
		while(!z.empty())
		{
			int i=z.top().second;
			z.pop();
			for(int q=head[i];q;q=x[q].nex)
			{
				int o=x[q].to;
	            if(vis[o]==1)continue;
			    vis[o]=1;
			    if(dis[o]>dis[i]+x[q].dis)
			    {
			    	dis[o]=dis[i]+x[q].dis;
			    	z.push(make_pair(dis[o],o));
			    }
			}
		}
		cout<<dis[n];
		return 0;
	}
}
signed main()
{
	long long n,m;
	for(long long q=1;q<=2;q++)d[q]=read();
	build(1,2,1);
	for(long long q=1;q<=1;q++)//吉司机线段树实现
	{
		long long a=3,l=1,r=2,k;
		if(a==1)
		{
			jj(l,r,1,n);
		}
		else if(a==2)
		{
			k=read();
			min(l,r,1,k);
		}
		else if(a==3)
		{
			printf("%lld\n",getsum(l,r,1));
		}
		else if(a==4)
		{
			printf("%lld\n",getmax(l,r,1));
		}
		else
		{
			printf("%lld\n",getlastmax(l,r,1));
		}
	}
	return 0;
}