#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 105
#define INF 0x3f3f3f3f3f3f3f3fLL
#define E 405 //有并查集，连接每个节点的边最多4条
#define MOD 100000
typedef long long ll;

typedef struct edge {
	int to;
	int next;
	long long weight;
}Edge;

int queue[E];
Edge map[E];
int edge_cnt;
int vis[M];
ll dist[M];
int head[M];
int count[M];
int path[M];

void addEdge(int u, int v, ll w) {
	map[edge_cnt].to = v;
	map[edge_cnt].weight = w;
	map[edge_cnt].next = head[u];
	head[u] = edge_cnt++;
}
void init() {
	edge_cnt = 0;
	memset(dist, 0x3f, sizeof(dist));
	memset(vis, 0, sizeof(vis));
	memset(head, -1, sizeof(head));
	memset(count, 0, sizeof(count));
	for (int i = 0; i < M; i++) {
		path[i] = i;
	}
}
int find(int x) {
	if (path[x] != x) {
		int t = find(path[x]);
		path[x] = t;
		return t;
	}
	return x;
}

void spfa(int s, int n) {
	dist[s] = 0;
	int left = 0, right = 0;
	queue[right++] = s;
	vis[s] = 1;
	whil...