#include 
using namespace std;
typedef long long ll;
const int N=300086;
typedef pair PII;

int n,m,s1;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
const int INF=100086;
int a,b,res=0,maxx; 
int p[INF],s[INF]; //存储每个点的祖宗节点
string op;
// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void init(int n)
{
    for(int i=0; i<=n; i++)
    {
        p[i] = i;
    }
}
void uni(int a,int b)
{
    
		// cin>>a>>b;
	if(find(a)==find(b))return;
	p[find(a)]=find(b);
	
}
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
void dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue, greater> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.po...