/*
I he so I pass, I pass because I he.
Not he Can't pass, Not pass because Not he.
----------------
Author: cnyz
----------------
Looking! The blitz loop this planet to search way.
Only my RAILGUN can shoot it. 今すぐ
*/
#include<bits/stdc++.h>
using namespace std;

typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define Online 1
#define enter pc('\n')
#define space pc(' ')
const int MAXL=1<<22;
char i_str[MAXL],o_str[MAXL],*i_s,*i_t;
int o_t;
inline char gc() {
    if(!Online) return getchar();
    if(i_s==i_t) {
        i_s=i_str;
        i_t=i_s+fread(i_str,1,MAXL,stdin);
        return i_s==i_t?EOF:*i_s++;
    } else return *i_s++;
}
inline void gs(char *s) {
    *s=gc();
    while(*s==' '||*s=='\n')*s=gc();
    while(*s!=' '&&*s!='\n')*++s=gc();
    *s='\0';
}
inline int read() {
    int x=0,f=0;
    char ch=gc();
    for(; ch<'0'||ch>'9'; ch=gc())
        if(ch=='-')f=1;
    for(; ch>='0'&&ch<='9'; ch=gc())
        x=(x<<1)+(x<<3)+(ch^48);
    return f?~x+1:x;
}
inline double readdb() {
    double x=0;
    int f=0;
    char ch=gc();
    for(; ch<'0'||ch>'9'; ch=gc())
        if(ch=='-')f=1;
    for(; ch>='0'&&ch<='9'; ch=gc())
        x=x*10+(ch^48);
    if(ch=='.') {
        ch=gc();
        for(double y=0.1;ch>='0'&&ch<='9';ch=gc(),y*=0.1)
            x=x+y*(ch^48);
    }
    return f?-x:x;
}
#define WDNMD fwrite(o_str,1,o_t,stdout),o_t=0
inline void pc(char x) {
    if(!Online) {
        putchar(x);
        return;
    }
    o_str[o_t++]=x;
    if(o_t==MAXL)WDNMD;
}
inline void write(int x) {
    if(x<0)x=-x,pc('-');
    if(x>9)write(x/10);
    pc(x%10^48);
}
inline void chkmax(int &x,int y) {
    if(x<y) x=y;
}
inline void chkmin(int &x,int y) {
    if(x>y) x=y;
}

void spfa() {
    queue<int> q;
    q.push(1);
    for(int i=2;i<=n;i++) dis[i]=1e18;
    dis[1]=0;
    while(q.size()) {
        int u=q.front();
        q.pop();
        for(auto i:G[u]) {
            int v=i.fi,d=i.se;
            if(dis[v]>dis[u]+d) dis[v]=dis[u]+d,q.push(v);
        }
    }
}

void dij() {
    q.push(mp(0,1));
    for(int i=2;i<=n;i++) dis[i]=1e18;
    dis[1]=0;
    while(q.size()) {
        int u=q.top().se;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:G[u]) {
            int v=i.fi,d=i.se;
            if(dis[v]>dis[u]+d) {
                dis[v]=dis[u]+d;
                q.push(mp(-dis[v],v));
            }
        }
    }
}

void Prim() {
    for(int i=1;i<=n;i++) dis[i]=1e18;
    dis[1]=0;
    for(int i=1;i<=n;i++) {
        ll mi=1e18;int id=0;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&mi>=dis[j]) id=j,mi=dis[j];
        vis[id]=1;ans+=dis[id];
        for(auto v:G[id])
            if(!vis[v.fi])
                if(v.se<=dis[v.fi])
                    dis[v.fi]=v.se;
    }
}