// T must define < and +
// V: max number of vertex [0~V-1]
template<typename T,size_t V,bool Directed=true,
         T INF=T(0x3f3f3f3f),T ZERO=T(0)>
struct G {
    typedef pair<T,int> PTI;
    vector<PTI> g[V];
    T dis[V];
    int vis[V];
    int n;
    void init(int n_)
    {
        n=n_;
        for(int i=0;i<n;i++) g[i].clear();
    }
    void addedge(int u,int v,T w)
    {
        g[u].emplace_back(w,v);
        if(!Directed) g[v].emplace_back(w,u);
    }
    void dijkstra(int st,int ed=-1) // ed=-1 no destination
    {
        for(int i=0;i<n;i++) dis[i]=INF,vis[i]=0;
        priority_queue<PTI,vector<PTI>,greater<PTI> > qu;
        dis[st]=ZERO;
        qu.emplace(ZERO,st);
        while(!qu.empty())
        {
            PTI p=qu.top(); qu.pop();
            int u=p.second;
            if(vis[u]) continue;
            vis[u]=1;
            if(u==ed) break;
            for(auto [w,v]:g[u])
            {
                if(vis[v]) continue;
                T nd=dis[u]+w;
                if(nd<dis[v])
                {
                    dis[v]=nd;
                    qu.emplace(nd,v);
                }
            }
        }
    }
};

    /* Debug ------------------------------------ 
       T need to define function
       ostream& operator<<(ostream& out, T rhs);  */
    void show()
    {
        cout<<"Dijkstra:----------------------\n";
        cout<<"id:";
        for(int i=0;i<n;i++) cout<<'\t'<<i;
        cout<<'\n';
        cout<<"dis:";
        for(int i=0;i<n;i++) cout<<'\t'<<dis[i];
        cout<<'\n';
        cout<<"vis:";
        for(int i=0;i<n;i++) cout<<'\t'<<vis[i];
        cout<<'\n';
        cout<<"-------------------------------\n\n";
    }

// must define < for T
// M: max size of heap
// MK: max size of key
template<typename T,size_t M>
struct Heap
{
	typedef pair<T,int> PTI;
	T h[M+1];
	int key[M+1]; // key[i] is unique and in [0~M-1] 
	int pos[M];   // position of elememt which key is i
	int n;        // number of node in the current heap
	void init() { n=0; }
	void push(T x,int k)
	{ 
		h[++n]=x; key[n]=k; pos[k]=n; swim(n); 
	}
	PTI pop()
	{
		T res=h[1]; int k=key[1]; 
		h[1]=h[n]; key[1]=key[n--]; pos[key[1]]=1;
		sink(1);
		return {res,k};
	}
	// decrease key to val
	void dec(int k,T val) // check key in [0~n-1]
	{
		int p=pos[k];
		T oldval=h[p];
		if(val<oldval) { h[p]=val; swim(p); }
	}
    bool empty() { return n==0; }
	/* Helper ----------------------------------- */
	void sink(int p)
	{
		int q=p<<1; T x=h[p]; int k=key[p];
		while(q<=n)
		{
			if(q<n&&h[q+1]<h[q]) q++;
			if(!(h[q]<x)) break; // h[q]>=x
			h[p]=h[q]; key[p]=key[q]; pos[key[p]]=p;
			p=q; q=p<<1;
		}
		h[p]=x; key[p]=k; pos[k]=p;
	}
	void swim(int p)
	{
		int q=p>>1; T x=h[p]; int k=key[p];
		while(q&&x<h[q])
		{ 
			h[p]=h[q]; key[p]=key[q]; pos[key[p]]=p;
			p=q; q=p>>1;
		}
		h[p]=x; key[p]=k; pos[k]=p;
	}
};

// T must define <
// V: max number of vertex [0~V-1]
template<typename T,size_t V,bool Directed=true;
         T INF=T(0x3f3f3f3f),T ZERO=T(0)>
struct Dijkstra {
	typedef pair<T,int> PTI;
	vector<PTI> g[V];
	T dis[V];
	int vis[V];
	int n;
	Heap<T,V> heap;
	void init(int n_)
	{
		n=n_;
		for(int i=0;i<n;i++) g[i].clear();
	}
	void addedge(int u,int v,T w)
	{
		g[u].emplace_back(w,v);
		if(!Directed) g[v].emplace_back(w,u);
	}
	void solve(int st,int ed=-1) // ed=-1 no destination
	{
		for(int i=0;i<n;i++) dis[i]=INF,vis[i]=0;
		heap.init();
		dis[st]=ZERO;
		heap.push(ZERO,st);
		while(!heap.empty())
		{
			PTI p=heap.pop();
			int u=p.second;
			if(vis[u]==2) continue;
			vis[u]=2;
			if(u==ed) break;
			for(auto [w,v]:g[u])
			{
				if(vis[v]==2) continue;
				T nd=dis[u]+w;
				if(nd<dis[v])
				{
					dis[v]=nd;
					if(!vis[v]) heap.push(nd,v),vis[v]=1;
					else heap.dec(v,nd);
				}
			}
		}
	}
};

    /* Debug ------------------------------------ 
       T need to define friend function
       ostream& operator<<(ostream& out, T rhs);  */
    void show()
    {
        cout<<"Dijkstra:----------------------\n";
        cout<<"id:";
        for(int i=0;i<n;i++) cout<<'\t'<<i;
        cout<<'\n';
        cout<<"dis:";
        for(int i=0;i<n;i++) cout<<'\t'<<dis[i];
        cout<<'\n';
        cout<<"vis:";
        for(int i=0;i<n;i++) cout<<'\t'<<vis[i];
        cout<<'\n';
        cout<<"-------------------------------\n\n";
    }