#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300086;
typedef pair<int, int> PII;
int n,m,s,t2;      // 点的数量
int h[N], w[N], e[N], ne[N], idx,cost[N];       // 邻接表存储所有边
int cnt[N];
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
void add(int a,int b,int c,int d)
{
	e[idx]=b,w[idx]=c,cost[idx]=d,ne[idx]=h[a],h[a]=idx++;
}
class pp
{
public:
    int fir;
    int sec;
    int cos;
    pp(int a,int b,int c):fir(a),sec(b),cos(c){}
     bool operator>(const pp &p)const
     {
        if(fir==p.fir)
        {
            return cos>p.cos;
        }
        else
        {
            return fir>p.fir;
        }
     }
};
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dij()
{
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0x3f, sizeof cnt);
    dist[s] = 0;
    cnt[s]=0;
    priority_queue<pp, vector<pp>, greater<pp>> heap;
    heap.push({0, s,0});      // fi...