//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

#define maxn 205
#define maxm 1010
#define INF 0x3f3f3f3f
#define for_(i,a,b) \
    for(int i = (a); i < (b);i++)

struct node
{
    int u, v, w;
}edges[maxm];

unordered_map<int,int> G[maxn];

bool cmp(const node& l, const node& r) {
    return l.w < r.w;
}

#define MODK 100000
int fa[maxn];
int dist[maxn];
int modk[maxm];
bool vis[maxn];

int n, m;

void getmodk(int k) {
    int sum = 1;
    for (int i = 0; i < k; i++)
    {
        modk[i] = sum;
        sum = (sum * 2) % MODK;
    }
}

void init() {
    for_(i, 0, maxn) fa[i] = i;
    for_(i, 0, maxn) dist[i] = IN...